Сортировка — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Перенаправление на Сортировки)
 
(не показано 25 промежуточных версий 5 участников)
Строка 1: Строка 1:
<wikitex>
+
#перенаправление [[Сортировки]]
{{в разработке}}
 
''Сортировкой'' называется процесс упорядочивания множества объектов по какому-либо признаку.
 
 
 
Обычно таким признаком служит лексикографический номер.
 
 
 
блаблабла
 
 
 
== Классификация сортировок ==
 
 
 
Будем рассматиривать сортировки массива из $n$ элементов множества $A$,
 
причем на $A$ должно быть выполнено [[Бинарное отношение|отношение эквивалентности]].
 
=== Время работы. ===
 
 
 
Эта классификация является самой важной. В основном временные оценки бывают $O(n \log n)$ и $O(n^2)$.
 
* Квадратичные. Такие сортировки самые простые в понимании.
 
** [[Сортировка пузырьком| Сортировка пузырьком (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)]]
 
** [[Сортировка слиянием с использованием О(1) дополнительной памяти|Модифицированная сортировка слиянием]]
 
** [[Сортировка кучей|Пирамидальная сортировка (Heap Sort)]]
 
 
 
 
 
* $O(n)$
 
 
 
</wikitex>
 
 
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Сортировки]]
 

Текущая версия на 10:49, 4 июня 2015

Перенаправление на: