Файл: Алгоритмы сортировки данных.pdf

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

Данный алгоритм можно ускорить при помощи использования бинарного поиска для нахождения места текущему элементу в отсортированной части. Проблема с долгим сдвигом массива вправо решается при помощи смены указателей^[16] [2].

2.1.4. Гномья сортировка

Гномья сортировка является алгоритмом сортировки, похожим на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков, описанного на странице книги Дика Груна «Гномья сортировка».

Концептуально алгоритм прост и не требует вложенных циклов. На практике алгоритм может работать так же быстро, как и сортировка вставками^[17].

Алгоритм находит первое место, где два соседних элемента стоят в неправильном порядке и меняет их местами. Он пользуется тем фактом, что обмен может породить новую пару, стоящую в неправильном порядке, только до или после переставленных элементов. Он не допускает, что элементы после текущей позиции отсортированы, таким образом, нужно только проверить позицию до переставленных элементов [4, 6]^[18].

2.1.5. Сортировка слиянием

При сортировке слиянием первая и вторая половину списка выстраиваются отдельно, а затем объединяются упорядоченные списки.

Для решения задачи сортировки эти три этапа выглядят так:

1. Сортируемый массив разбивается на две части примерно одинакового размера;
2. Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
3. Два упорядоченных массива половинного размера соединяются в один^[19] [3].

2.1.6. Сортировка с помощью двоичного дерева

Сортировка с помощью двоичного дерева является универсальным алгоритмом сортировки, который заключается в построении двоичного дерева поиска по ключам массива, с последующей сборкой результирующего массива путем обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путем непосредственного чтения с потока (например, из файла, сокета или консоли)^[20] [7].

2.1.7. Сортировка Timsort

Сортировка Timsort представляет собой комбинированный алгоритм из сортировки вставками и сортировки слиянием. Основная идея алгоритма заключается в том, что алгоритму входной массив разделяется на подмассивы, каждый подмассив сортируется сортировкой вставками, после чего отсортированные подмассивы собираются в единый массив с помощью модифицированной сортировки слиянием^[21] [2].

2.1.8. Сортировка подсчетом

Сортировка подсчетом является алгоритмом сортировки, в котором используется диапазон чисел сортируемого массива для подсчета совпадающих элементов. Применение сортировки подсчетом целесообразно лишь тогда, когда сортируемые числа имеют диапазон возможных значений, достаточно малый по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. Необходимость сортировки внутри ячеек лишает алгоритм смысл, так как каждый элемент придется просматривать более одного раза^[22] [4].

2.1.9. Блочная сортировка

Блочная сортировка, также называемая корзинной сортировкой, является алгоритмом сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков так, чтобы все элементы в каждом следующем по порядку блоке были всегда меньше или больше, чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения^[23] [9].

2.1.10. Поразрядная сортировка

Поразрядная сортировка, также называемая цифровой сортировкой является алгоритмом сортировки за линейное время. Числа сортируются по разрядам. Существует два варианта: least significant digit (LSD) и most significant digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке все наоборот. При LSD сортировке получается следующий порядок: короткие ключи идут раньше длинных, ключи одного размера сортируются по алфавиту, это совпадает с нормальным представлением чисел. При MSD сортировке получается алфавитный порядок, который подходит для сортировки строк^[24] [2].

2.2. Алгоритмы неустойчивой сортировки

2.2.1. Сортировка выбором

Сортировка выбором может быть как устойчивой, так и неустойчивой.

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

Для реализации устойчивости алгоритма необходимо при обмене значений минимальный элемент непосредственно вставлять в первую неотсортированную позицию, не меняя порядок остальных элементов^[25] [1].

2.2.2. Сортировка Шелла и сортировка расческой

Сортировка Шелла представляет собой алгоритм сортировки, который является усовершенствованным вариантом сортировки вставками. Идея метода Дональда Шелла состоит в сравнении элементов, которые стоят не только рядом, но и на определенном расстоянии друг от друга. Другими словами, данный вид сортировки представляет собой сортировку вставками, но с предварительными «грубыми» проходами^[26].

Аналогичный метод усовершенствования «пузырьковой» сортировки называется «сортировка расческой». Сортировка расческой является довольно упрощенным алгоритмом сортировки, который был изначально спроектирован Влодзимежом Добосевичем в 1980 году. Позднее он был переоткрыт и популяризован в статье Ричарда Бокса и Стивена Лэйси в журнале Byte Magazine в апреле 1991 года. Сортировка расческой улучшает сортировку пузырьком, и конкурирует с подобными быстрой сортировке алгоритмами. Основная идея алгоритма заключается устранении черепах, или маленьких значений в конце списка, которые крайне замедляют сортировку пузырьком. Кролики противопоставлены черепахам, являясь большими значениями в начале списка, не представляющими проблемы для сортировки пузырьком^[27].

В сортировке пузырьком, когда сравниваются два элемента, промежуток между ними равен 1. Основная идея сортировки расческой в том, что этот промежуток может быть гораздо больше, чем единица. Сортировка Шелла также основана на этой идее^[28] [4, 7, 10].

2.2.3. Пирамидальная сортировка

Пирамидальная сортировка может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает или тонет по многим путям. Сортировка пирамидой использует бинарное сортирующее дерево. Алгоритм сортировки будет состоять из двух основных шагов: элементы массива выстраиваются в виде сортирующего дерева, после чего удаляются элементы из корня по одному за раз и дерево перестраивается^[29] [8].

2.2.4. Плавная сортировка

Плавная сортировка является алгоритмом сортировки выбором, разновидностью пирамидальной сортировки, которая была разработана Э. Дейкстрой в 1981 году. Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи. В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо. Куча состоит из последовательности куч, размеры которых равны одному из чисел Леонардо, а корни хранятся в порядке возрастания^[30] [1].

2.2.5. Быстрая сортировка

Быстрая сортировка, также называемая сортировкой Хоара, является широко известным алгоритмом сортировки, который был разработан английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году. Быстрая сортировка является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена и его вариантов пузырьковой сортировки и шейкерной сортирови, известных, помимо прочего, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов^[31] [4].

2.2.6. Сортировка Introsort

Introsort или интроспективная сортировка является алгоритм сортировки, который был предложен Дэвидом Мюссером в 1997 году. Он использует быструю сортировку и переключается на пирамидальную сортировку, когда глубина рекурсии превысит некоторый заранее установленный уровень (например, логарифм от числа сортируемых элементов). Так как оба алгоритма используют сравнения, этот алгоритм также принадлежит классу сортировок на основе сравнений^[32] [2].

2.3. Прочие алгоритмы сортировки

Bogosort, также называемая случайной сортировкой, сортировкой ружья или обезьяньей сортировкой является очень неэффективным алгоритмом сортировки. Ее используют только в образовательных целях, противопоставляя другим, более реалистичным алгоритмам. Если bogosort использовать для сортировки колоды карт, то сначала в алгоритме нужно проверить, лежат ли все карты по порядку, и если не лежат, то случайным образом перемешать ее, проверить лежат ли теперь все карты по порядку, и повторять процесс, пока не отсортируется колода^[33].

Блинная сортировка является алгоритмом сортировки, с единственной допустимой операцией — переворотом элементов последовательности до какого-либо индекса. В отличие от традиционных алгоритмов, в которых минимизируют количество сравнений, в блинной сортировке требуется сделать как можно меньше переворотов. Процесс можно визуально представить в виде стопки блинов, которую тасуют путем взятия нескольких блинов сверху и их переворачивания^[34].