Одной из наиболее известных и популярных сортировок, не имеющих в своём основании сравнений, является – сортировка подсчётом.

Сортировка подсчётом – алгоритм сортировки, в котором используется диапазон чисел сортируемого массива для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000

Рисунок 1 – «Визуализация алгоритма сортировки подсчётом»

Помимо таких популярных сортировок, как сортировка подсчётом – существуют менее популярные. Одним из таких алгоритмов является алгоритм блочной сортировки.

Блочная сортировка – алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок сортируется отдельно. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.

Рисунок 2 – «Визуализация блочного алгоритма сортировки»

Последним разбираемым алгоритмом сортировок без сравнений в этой статье окажется поразрядная сортировка. Её автором является Холлерит Герман – создатель табулирующей системы.

Поразрядная сортировка – сортировка, алгоритм которой заключается в том, что исходное множество отдельно сортируется блочной сортировкой (или подсчётом) по каждому разряду, начиная с младшего. Поразрядная сортировка позволяет сохранить линейную оценку времени, когда ключ состоит из нескольких компонентов, имеющих небольшое множество возможных значений. В качестве примера можно привести символьные строки ограниченной длины или числа ограниченной разрядности. Компоненты могут быть различных типов, например дата (день; месяц; год), при условии, что область значения года искусственно ограничена

Рисунок 3 – «Неотсортированный массив»

Рисунок 4 – «Результат сортировки по разряду единиц»

Р исунок 5 – «Результат сортировки по разряду десятков»

Р исунок 6 – «Результат сортировки по разряду сотен»

Рисунок 7 – «Общий результат сортировки»

В качестве заключения нужно обозначить, что для каждой сортировки можно найти необходимое применение. В том числе для тех, в которых нет сравнений. Самое главное, чтобы в проектах они использовались в правильных местах и только по назначению.

Так как главной чертой разобранных алгоритмов является отсутствие элемента сравнения значений между друг другом – алгоритмы данных сортировок используют иные возможности, для проведения процесса сортирования данных. В основном используются свойства данных для этого. Самыми распространёнными из таких сортировок являются: блочная сортировка, поразрядная сортировка и сортировка подсчётом.

Данные алгоритмы часто более эффективны, чем алгоритмы, в которых данные сортируются с участием сравнений, поскольку, зачастую, каждый элемент данных сравнивается с каждым.

Однако главным недостатком сортировок без сравнений является их специализированность и куда более меньшая универсальность. Свойства данных очень сильно ограничивают применимость данных сортировок. Однако если в решаемой задаче возникает такая уникальная ситуация – в таком случае использование подобной сортировки будет оправдано и приведёт к оптимизации работы.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Учебники, монографии, брошюры

1. Огнева, М. В. Программирование на языке С++: практический курс : учебное пособие для среднего профессионального образования / М. В. Огнева, Е. В. Кудрина. – Москва : Издательство Юрайт, 2023. – 335 с.

2. Ландовский, В. В. Алгоритмы обработки данных / В. В. Ландовский. – 2-е. – Новосибирск : Издательство ЛитРес, 2022. – 66 c.

3. Макарова, Н. В. Информатика: Учебник для вузов. / Н. В. Макарова, В. Б. Волков. – 1-е изд. – Санкт-Петербург : "Издательский дом ""Питер""", 2021. – 576 c.

Интернет-ресурсы

1. Non Comparsion based Sorting Algorighms [Электронныйресурс] – URL https://iq.opengenus.org/non-comparison-based-sorting/ (Датаобращения 04.05.2023)

2. Non-Comparsion Sorting Algorithms [Электронныйресурс] – URL https://pages.cs.wisc.edu/~paton/readings/Old/fall01/LINEAR-SORTS.html (Датаобращения 05.05.2023)

3. Difference between Comparison and Non-Comparison Sorting Algorithms [Электронныйресурс] – URL https://www.krayonnz.com/user/doubts/detail/632bf743befe760055b67ae9/what-is-the-difference-between-Comparison-and-Non-Comparison-Sorting-Algorithms (Датаобращения 06.05.2023)

Код для цитирования: Скопировать