Сортировка

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

Разработано большое количество алгоритмов сортировки, реализованных на языках программирования высокого уровня. Реализации оперируют в качестве элементов множества элементами структуры данных, наиболее подходящей для того или иного алгоритма (в наиболее распространенной ситуации – одномерного массива). Отношение порядка на множестве может быть введено разными способами. Для т. н. примитивных типов (числа, символы) обычно существует естественный порядок (соответственно по возрастанию числа, по возрастанию значения кода символа в ASCII или Unicode). Для пользовательских типов данных необходимо такой порядок задать явно. Часто конструкции языка программирования позволяют это сделать несколькими способами.

Среди характеристик, важных для применения реализации того или иного алгоритма сортировки, следует выделить временну́ю сложность, объем дополнительно используемой памяти, т. н. устойчивость [свойство алгоритма сохранять взаимный порядок равных элементов (не переставлять их друг относительно друга в ходе работы алгоритма)].

Несложно доказывается, что при условии использования только лишь попарных сравнений элементов множества никакой алгоритм не может использовать в худшем случае меньше, чем ${\displaystyle \log _{2}n!}$ таких сравнений для сортировки множества из ${\displaystyle n}$ элементов. Согласно формуле Стирлинга, ${\displaystyle \log _{2}n!=n\,\log _{2}n+O(n)}$, что даёт нижнюю оценку для сложности произвольного алгоритма сортировки, основанного на сравнениях (англ. comparison sort). См. также «О большое».

Известна поразрядная сортировка – алгоритм, учитывающий структуру записи элементов множества, а именно использующий возможность разбить их на сравнимые фрагменты (разряды) и, таким образом, сравнивать элементы множества не непосредственно, а поразрядно лексикографически. Временна́я сложность поразрядной сортировки пропорциональна ${\displaystyle w\cdot n}$, где ${\displaystyle w}$ – число разрядов в записи элементов множества.

Примеры:

1. «Квадратичные» сортировки. Название связано с тем, что в худшем случае для сортировки множества из ${\displaystyle n}$ элементов они требуют примерно ${\displaystyle n^{2}}$ попарных сравнений (с точностью до множителя и членов меньшего порядка). К таковым относятся сортировка пузырьком, сортировка выбором, сортировка вставками. Используются в основном в учебных целях либо для сортировки множеств, содержащих небольшое количество элементов.
2. Сортировка слиянием (англ. Mergesort). Асимптотически оптимальный алгоритм, поскольку его сложность может быть оценена как ${\displaystyle O(n\,\log _{2}n)}$. Кроме того, сортировка слиянием пригодна для использования в качестве т. н. внешней сортировки в ситуации, когда сортируемое множество не помещается в оперативной памяти целиком.
3. Быстрая сортировка (англ. Quicksort; Хоар, 1960). Несмотря на то что не является асимптотически оптимальным алгоритмом, для многих исходных данных выполняется быстрее, например, сортировки слиянием. C доработками используется в библиотеках Java.