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

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

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

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

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

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

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

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

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

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

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

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

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

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

Этот алгоритм работает по принципу «разделяй и властвуй».

Здесь мы делим список ровно пополам и продолжаем это делать, пока в нем не останется только один элемент. Затем мы объединяем уже упорядоченные части нашего списка. Мы продолжаем это делать, пока не получим отсортированный список со всеми элементами несортированного входного списка.

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

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

В этом алгоритме мы разбиваем список при помощи опорного элемента, сортируя значения вокруг него.

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

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

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

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

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