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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 31: Строка 31:
 
{|class="wikitable"
 
{|class="wikitable"
 
|+
 
|+
!width="20%"|Название !!width="10%"| Лучшее время !!width="10%"| Среднее !!width="10%"| Худшее !!width="10%"| Память !! width="10%"|Стабильность !!width="30%"| Описание
+
!width="15%"|Название !!width="8%"| Лучшее время !!width="8%"| Среднее !!width="8%"| Худшее !!width="8%"| Память !! width="8%"|Стабильность !! width="10%| Обмены (в среднем) !! "width="35%"| Описание
 
|- align = "center"
 
|- align = "center"
 
|[[Сортировка пузырьком| Сортировка пузырьком <br>(Bubble Sort)]]
 
|[[Сортировка пузырьком| Сортировка пузырьком <br>(Bubble Sort)]]
Строка 39: Строка 39:
 
|$O(1)$
 
|$O(1)$
 
|Да
 
|Да
 +
|$O(n^2)$
 
|Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами.
 
|Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами.
 
|- align = "center"
 
|- align = "center"
Строка 47: Строка 48:
 
|$O(1)$
 
|$O(1)$
 
|Да
 
|Да
 +
|$O(n^2)$
 
|На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован.
 
|На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован.
 
|- align = "center"
 
|- align = "center"
Строка 55: Строка 57:
 
|$O(1)$
 
|$O(1)$
 
|Нет
 
|Нет
 +
|$O(n)$
 
|На каждом $i$-ом шаге алгоритма находим $i$-ый минимальный элемент и меняем его местами с $i$-ым элементом в массиве.
 
|На каждом $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.
 
|}
 
|}
* Квадратичные. Такие сортировки самые простые в понимании.
 
** [[Сортировка пузырьком| Сортировка пузырьком (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.
 
 
  
 
* Прочие сортировки.
 
* Прочие сортировки.
Строка 75: Строка 119:
 
** [[Сортировка Хэна (или Хана?)|Сортировка Хэна]] - упоротая сортировка целых чисел с оценкой $O(n \log \log n)$
 
** [[Сортировка Хэна (или Хана?)|Сортировка Хэна]] - упоротая сортировка целых чисел с оценкой $O(n \log \log n)$
  
 
=== Затраты памяти ===
 
 
* $O(1)$. Обычно такие сортировки используют обмены элементов.
 
** [[Сортировка пузырьком| Сортировка пузырьком (Bubble Sort)]]
 
** [[Сортировка вставками| Сортировка вставками (Insertion Sort)]]
 
** [[Сортировка выбором| Сортировка выбором (Selection Sort)]]
 
** [[Быстрая сортировка|Быстрая сортировка (Quick Sort)]]
 
** [[Сортировка слиянием с использованием О(1) дополнительной памяти|Модифицированная сортировка слиянием]]
 
** [[Сортировка кучей|Пирамидальная сортировка (Heap Sort)]]
 
 
 
* $O(n)$
 
  
 
</wikitex>
 
</wikitex>

Версия 14:49, 12 июня 2012

<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)$ Да $O(n^2)$ Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами.
Сортировка вставками
(Insertion Sort)
$O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ Да $O(n^2)$ На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован.
Сортировка выбором
(Selection Sort)
$O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ Нет $O(n)$ На каждом $i$-ом шаге алгоритма находим $i$-ый минимальный элемент и меняем его местами с $i$-ым элементом в массиве.
Быстрая сортировка
(Quick Sort)
$O(n \log n)$ $O(n \log n)$ $O(n^2)$
(маловероятно)
$O(\log n)$
(стек вызовов)
Нет $O(n \log n)$ Один из самых известных и широко используемых алгоритмов сортировки. Алгоритм состоит в выборе опорного элемента, разделении массива на 2 части относительно опорного и в сортировке полученных частей.
Сортировка слиянием
(Merge Sort)
$O(n \log n)$ $O(n \log n)$ $O(n \log n)$ $O(n)$ (обычная реализация)
$O(1)$
(модифицированная реализация)
Да $O(n \log n)$ Алгоритм состоит в разделении массива пополам, сортировки половин и их слиянии.
Пирамидальная сортировка
(Heap Sort)
$O(n \log n)$ $O(n \log n)$ $O(n \log n)$ $O(1)$ Нет $O(n \log n)$ Строим из массива кучу, по очереди извлекаем минимум кучи.
Сортировка с помощью бинарного дерева
(Tree Sort)
$O(n)$ $O(n \log n)$ $O(n \log n)$ $O(n)$ Да $O(n)$ Добавляем по очереди вершины в сбалансированное дерево поиска, проходим по всем вершинам в порядке возрастания.
Карманная сортировка
(Bucked Sort)
$O(n)$ $O(n \log n)$ $O(n^2)$ $O(n)$ Да - распихиваем элементы в $k$ карманов, сортируем элементы внутри карманов, из каждого кармана данные записываются в массив в порядке разбиения.
Цифровая сортировка
(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>

Ссылки

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