Сортировка

Материал из Викиконспекты
Перейти к: навигация, поиск

<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 + k)$, где $k$ - длина диапазона.
    • Сортировка Хэна - упоротая сортировка целых чисел с оценкой $O(n \log \log n)$


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


  • $O(n)$

</wikitex>

Ссылки