Сортировка

<wikitex>

Эта статья находится в разработке!

Сортировкой называется процесс упорядочивания множества объектов по какому-либо признаку.

Обычно таким признаком служит лексикографический номер.

Классификация сортировок

Будем рассматиривать сортировки массива из $n$ элементов множества $A$, причем на $A$ должно быть выполнено отношение эквивалентности.

Время работы.

Эта классификация является самой важной. Оценивают худшее время алгоритма, среднее и лучшее. У большинства алгоритмов временные оценки бывают $O(n \log n)$ и $O(n^2)$.

Память

Параметр сортировки, показывающий, сколько дополнительной памяти требуется алгоритму. Сюда входят и дополнительный массив, и переменные, и затраты на стек вызовов. Обычно затраты бывают $O(1)$, $O(\log n)$, $O(n)$.

Стабильность

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

Количество обменов

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

Сравнение сортировок

Название	Лучшее время	Среднее	Худшее	Память	Стабильность	Описание
Сортировка пузырьком (Bubble Sort)	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Да	Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами.
Сортировка вставками (Insertion Sort)	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Да	На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован.
Сортировка выбором (Selection Sort)	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	Нет	На каждом $i$-ом шаге алгоритма находим $i$-ый минимальный элемент и меняем его местами с $i$-ым элементом в массиве.

• Квадратичные. Такие сортировки самые простые в понимании.
  • Сортировка пузырьком (Bubble Sort) - Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами.
  • Сортировка вставками (Insertion Sort) - На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован.
  • Сортировка выбором (Selection Sort) - На каждом $i$-ом шаге алгоритма находим $i$-ый минимальный элемент и меняем его местами с $i$-ым элементом в массиве.

• $O(n \log n)$. Нормальное время сортировки. Это минимальное время, за которое можно отсортировать массив, используя только сравнения.
  • Быстрая сортировка (Quick Sort). Один из самых известных и широко используемых алгоритмов сортировки. Алгоритм состоит в выборе опорного элемента, разделении массива на 2 части относительно опорного и в сортировке полученных частей.
  • Сортировка слиянием (Merge Sort). Алгоритм состоит в разделении массива пополам, сортировки половин и их слиянии.
  • Пирамидальная сортировка (Heap Sort). Строим из массива кучу, по очереди извлекаем минимум кучи.
  • Карманная сортировка (Bucked Sort) - распихиваем элементы в $k$ карманов, сортируем элементы внутри карманов, из каждого кармана данные записываются в массив в порядке разбиения.
  • Цифровая сортировка (Radix Sort) - сортировка, аналогичная карманной. карманы в данном случае - цифры от 0 до 9.

• Прочие сортировки.
  • Сортировка подсчетом. Сортировка объектов, ключи которых входят в заранее известный диапазон целых чисел. Время работы - $O(n + k)$, где $k$ - длина диапазона.
  • Сортировка Хэна - упоротая сортировка целых чисел с оценкой $O(n \log \log n)$

Затраты памяти

• $O(1)$. Обычно такие сортировки используют обмены элементов.
  • Сортировка пузырьком (Bubble Sort)
  • Сортировка вставками (Insertion Sort)
  • Сортировка выбором (Selection Sort)
  • Быстрая сортировка (Quick Sort)
  • Модифицированная сортировка слиянием
  • Пирамидальная сортировка (Heap Sort)

• $O(n)$

</wikitex>

Ссылки

Википедия срывает покровы