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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Перенаправление на Сортировки)
 
(не показаны 22 промежуточные версии 5 участников)
Строка 1: Строка 1:
<wikitex>
+
#перенаправление [[Сортировки]]
{{в разработке}}
 
''Сортировкой'' называется процесс упорядочивания множества объектов по какому-либо признаку.
 
 
 
Обычно таким признаком служит лексикографический номер.
 
 
 
 
 
== Классификация сортировок ==
 
 
 
Будем рассматиривать сортировки массива из $n$ элементов множества $A$,
 
причем на $A$ должно быть выполнено [[Бинарное отношение|отношение эквивалентности]].
 
=== Время работы. ===
 
 
 
Эта классификация является самой важной. Оценивают худшее время алгоритма, среднее и лучшее.
 
У большинства алгоритмов временные оценки бывают $O(n \log n)$ и $O(n^2)$.
 
 
 
=== Память ===
 
 
 
Параметр сортировки, показывающий, сколько дополнительной памяти требуется алгоритму. Сюда входят и дополнительный массив, и переменные, и затраты на стек вызовов. Обычно затраты бывают $O(1)$, $O(\log n)$, $O(n)$.
 
 
 
=== Стабильность ===
 
 
 
''Стабильной сортировкой'' называется сортировка, не меняющая порядка объектов с одинаковыми ключами.
 
 
 
=== Количество обменов ===
 
 
 
Важный параметр, когда объекты имеют большой размер. В таком случае при большом кол-ве обменов время алгоритма заметно увеличивается.
 
 
 
== Сравнение сортировок ==
 
 
 
{|class="wikitable"
 
|+
 
!width="15%"|Название !!width="8%"| Лучшее время !!width="8%"| Среднее !!width="8%"| Худшее !!width="8%"| Память !! width="8%"|Стабильность !! width="10%| Обмены (в среднем) !! "width="35%"| Описание
 
|- align = "center"
 
|[[Сортировка пузырьком| Сортировка пузырьком <br>(Bubble Sort)]]
 
|$O(n)$
 
|$O(n^2)$
 
|$O(n^2)$
 
|$O(1)$
 
|Да
 
|$O(n^2)$
 
|Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами.
 
|- align = "center"
 
|[[Сортировка вставками| Сортировка вставками <br>(Insertion Sort)]]
 
|$O(n)$
 
|$O(n^2)$
 
|$O(n^2)$
 
|$O(1)$
 
|Да
 
|$O(n^2)$
 
|На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован.
 
|- align = "center"
 
|[[Сортировка выбором| Сортировка выбором<br> (Selection Sort)]]
 
|$O(n^2)$
 
|$O(n^2)$
 
|$O(n^2)$
 
|$O(1)$
 
|Нет
 
|$O(n)$
 
|На каждом $i$-ом шаге алгоритма находим $i$-ый минимальный элемент и меняем его местами с $i$-ым элементом в массиве.
 
|- align = "center"
 
|[[Быстрая сортировка|Быстрая сортировка<br> (Quick Sort)]]
 
|$O(n \log n)$
 
|$O(n \log n)$
 
|$O(n^2)$<br>(маловероятно)
 
|$O(\log n)$<br>(стек вызовов)
 
|Нет
 
|$O(n \log n)$
 
|Один из самых известных и широко используемых алгоритмов сортировки. Алгоритм состоит в выборе опорного элемента, разделении массива на 2 части относительно опорного и в сортировке полученных частей.
 
|- align = "center"
 
|[[Сортировка слиянием|Сортировка слиянием <br>(Merge Sort)]]
 
|$O(n \log n)$
 
|$O(n \log n)$
 
|$O(n \log n)$
 
|$O(n)$ (обычная реализация)<br>$O(1)$<br> ([[Cортировка слиянием с использованием O(1) дополнительной памяти|модифицированная реализация]])
 
|Да
 
|$O(n \log n)$
 
|Алгоритм состоит в разделении массива пополам, сортировки половин и их слиянии.
 
|- align = "center"
 
|[[Сортировка кучей|Пирамидальная сортировка <br>(Heap Sort)]]
 
|$O(n \log n)$
 
|$O(n \log n)$
 
|$O(n \log n)$
 
|$O(1)$
 
|Нет
 
|$O(n \log n)$
 
|Строим из массива кучу, по очереди извлекаем минимум кучи.
 
|- align = "center"
 
|[[Дерево поиска, наивная реализация|Сортировка с помощью бинарного дерева <br>(Tree Sort)]]
 
|$O(n)$
 
|$O(n \log n)$
 
|$O(n \log n)$
 
|$O(n)$
 
|Да
 
|$O(n)$
 
|Добавляем по очереди вершины в сбалансированное дерево поиска, проходим по всем вершинам в порядке возрастания.
 
|- align = "center"
 
|[[Карманная сортировка|Карманная сортировка <br>(Bucked Sort)]]
 
|$O(n)$
 
|$O(n \log n)$
 
|$O(n^2)$
 
|$O(n)$
 
|Да
 
| -
 
|распихиваем элементы в $k$ карманов, сортируем элементы внутри карманов, из каждого кармана данные записываются в массив в порядке разбиения.
 
|- align = "center"
 
|[[Цифровая сортировка|Цифровая сортировка <br>(Radix Sort)]]
 
|$O(n \log n)$
 
|$O(n \log n)$
 
|$O(n \log n)$
 
|$O(n)$
 
|Да
 
| -
 
|сортировка, аналогичная карманной. карманы в данном случае - цифры от 0 до 9.
 
|}
 
 
 
* Прочие сортировки.
 
** [[Сортировка подсчетом]]. Сортировка объектов, ключи которых входят в заранее известный диапазон целых чисел. Время работы - $O(n + k)$, где $k$ - длина диапазона.
 
** [[Сортировка Хэна (или Хана?)|Сортировка Хэна]] - упоротая сортировка целых чисел с оценкой $O(n \log \log n)$
 
 
 
 
 
</wikitex>
 
== Ссылки ==
 
 
 
[http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8| Википедия срывает покровы]
 
 
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Сортировки]]
 

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

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