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

В этом алгоритме мы создаем два сегмента нашего списка: один отсортированный, а другой несортированный.

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

Алгоритм сортировки выбором:
▪️ нерекурсивный;
▪️ может быть как устойчивым, так и неустойчивым;
▪️ преобразует входные данные без использования вспомогательной структуры данных (in place);
▪️ имеет сложность O(n^2);

Сортировка вставками

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

Алгоритм сортировки вставками:
▪️ нерекурсивный;
▪️ устойчивый;
▪️ преобразует входные данные без использования вспомогательной структуры данных (in place);
▪️ имеет сложность O(n^2);

Сортировка Шелла

Сортировка Шелла является оптимизированным вариантом сортировки вставками.

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

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

Алгоритм сортировки Шелла:
▪️ нерекурсивный;
▪️ устойчивый;
▪️ преобразует входные данные без использования вспомогательной структуры данных (in place);
▪️ имеет сложность O(n^2), но это также зависит от выбора длины интервала;

Пирамидальная сортировка («сортировка кучей»)

Как и в двух предыдущих алгоритмах, мы создаем два сегмента списка: отсортированный и несортированный.

В данном алгоритме для эффективного нахождения максимального элемента в неотсортированной части списка мы используем структуру данных «куча».

Метод heapify в примере кода использует рекурсию для получения элемента с максимальным значением на вершине.

Алгоритм пирамидальной сортировки:
▪️ нерекурсивный;
▪️ неустойчивый;
▪️ преобразует входные данные без использования вспомогательной структуры данных (in place);
▪️ имеет сложность O(nlog(n));