3. Сортировки. Назначение, типы, сравнение.

Алгоритм сортировки – алгоритм для упорядочивания элементов в списке (массиве).

Существуют разные алгоритмы сортировок по типу:

 Алгоритмы устойчивой сортировки:

 Сортировка пузырьком - для каждой пары индексов производится обмен, если элементы расположены не по порядку (алгоритмическая сложность O(n²)). Внутренний цикл снова и снова пробегает по массиву и сравнивает текущий элемент с предыдущим и если текущий меньше, переставляет его с предыдущим;

 Сортировка вставками – элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов (алгоритмическая сложность O(n) – лучшая, O(n²) – худшая и средняя);

 Сортировка слиянием – разделение списка элементов на две половины примерно одинакового размера, сортировка каждой части отдельно, соединение упорядоченных массива половинного размера в один – (алгоритмическая сложность всегда O(n log₂ n));

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

 Сортировка выбором – поиск наименьшего и наибольшего элемента и помещение его в начало или конец упорядоченного списка (алгоритмическая сложность всегда O(n²));

 Сортировка расческой (сложность алгоритма худшая - O(n²), лучшая – О(n log₂ n)) – улучшение сортировки пузырьком. Основная идея «расчёски» в том, чтобы первоначально брать достаточно большое расстояние между сравниваемыми элементами и по мере упорядочивания массива сужать это расстояние вплоть до минимального. Первоначальный разрыв между сравниваемыми элементами лучше брать с учётом специальной величины, называемой фактором уменьшения, оптимальное значение которой равно примерно 1,247. Сначала расстояние между элементами равно размеру массива, разделённого на фактор уменьшения (результат округляется до ближайшего целого). Затем, пройдя массив с этим шагом, необходимо поделить шаг на фактор уменьшения и пройти по списку вновь. Так продолжается до тех пор, пока разность индексов не достигнет единицы. В этом случае массив досортировывается обычным пузырьком.

 Сортировка Шелла – улучшение сортировки вставками, сравнение элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга, начальный шаг d = n / 2 (лучший случай O(n∙log²n), худший случай O(n²)). При сортировке Шелла сначала сравниваются и сортируются между собой значения, стоящие один от другого на расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d=1 (то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определенных случаях обеспечивается тем, что элементы «быстрее» встают на свои места.

 Быстрая сортировка – выбор опорного элемента в массиве, и его сравнение с остальными элементами в определенном порядке, равные и бОльшие элементы помещаются справа, меньшие – слева, затем рекурсивное применение вышеописанного (алгоритмическая сложность в лучшем и среднем случае O(n∙logn), худший случай O(n²)).

Общая идея:

- из массива выбирается опорный элемент – любой из элементов

- сравниваем все остальные элементы с опорным и переставляем так, чтобы разбить массив на три непрерывных отрезка, следующих друг за другом: меньше опорного, равные и больше

- Для меньших и больших значений делаем рекурсивный повтор;

 Пирамидальная сортировка – сортировка кучей (бинарное сортирующее дерево) – алгоритмическая сложность всегда O(n∙logn). Общая идея пирамидальной сортировки заключается в том, что сначала строится пирамида из элементов исходного массива, а затем осуществляется сортировка элементов. Массив можно отсортировать, если на его основе строить и перестраивать сортирующее дерево. 

Сортирующее дерево - дерево, у которого любой родитель больше (или меньше, смотря в какую сторону оно сортирующее) чем его потомки. Чтобы из обычного сделать сортирующее нужно двигаться от потомков вверх к родителям и если потомок больше родителя, то менять местами. Если такой обмен произошёл, опустившегося на один уровень родителя нужно сравнить с потомками ниже – может и там тоже будет повод для обмена.

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