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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 6: Строка 6:
 
Так как данные могут хранится в разных структурах, то и алгоритмы для каждой структуры могут отличаться. Например, при хранении данных в списке, нежели чем в массиве, сортировка слиянием потребует $O(n^2)$ времени и $O(1)$ памяти против $O(n \log n)$ и $O(n)$ с использованием массива; а вот сортировка пузырьком не изменится.
 
Так как данные могут хранится в разных структурах, то и алгоритмы для каждой структуры могут отличаться. Например, при хранении данных в списке, нежели чем в массиве, сортировка слиянием потребует $O(n^2)$ времени и $O(1)$ памяти против $O(n \log n)$ и $O(n)$ с использованием массива; а вот сортировка пузырьком не изменится.
  
Также есть алгоритмы параллельной сортировки данных (т.н. [[Сортирующие сети]]), время работу которых $O(\log n)$.  
+
Также есть алгоритмы параллельной сортировки данных (т.н. [[Сортирующие сети]]), время работы которых в лучшем случае $O(\log n)$.  
 
== Классификация сортировок ==
 
== Классификация сортировок ==
  
 
=== Время работы ===
 
=== Время работы ===
  
Эта классификация является самой важной. Оценивают худшее время алгоритма, среднее и лучшее.
+
Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее. Лучшее время - минимальное время работы алгоритма на каком-либо наборе, обычно этим набором является тривиальный $\big[ 1 \ldots n \big] $. Худшее время - наибольшее время.
 
У большинства алгоритмов временные оценки бывают $O(n \log n)$ и $O(n^2)$.
 
У большинства алгоритмов временные оценки бывают $O(n \log n)$ и $O(n^2)$.
  
 
=== Память ===
 
=== Память ===
  
Параметр сортировки, показывающий, сколько дополнительной памяти требуется алгоритму. Сюда входят и дополнительный массив, и переменные, и затраты на стек вызовов. Обычно затраты бывают $O(1)$, $O(\log n)$, $O(n)$.
+
Параметр сортировки, показывающий, сколько '''дополнительной''' памяти требуется алгоритму. Сюда входят и дополнительный массив, и переменные, и затраты на стек вызовов. Обычно затраты бывают $O(1)$, $O(\log n)$, $O(n)$.
  
=== #Стабильность ===
+
=== Стабильность ===
  
 
''Стабильной сортировкой'' называется сортировка, не меняющая порядка объектов с одинаковыми ключами.
 
''Стабильной сортировкой'' называется сортировка, не меняющая порядка объектов с одинаковыми ключами.
Строка 24: Строка 24:
 
=== Количество обменов ===
 
=== Количество обменов ===
  
Важный параметр, когда объекты имеют большой размер. В таком случае при большом кол-ве обменов время алгоритма заметно увеличивается.
+
Количество обменов может быть важным параметром в случае, если объекты имеют большой размер. В таком случае при большом количестве обменов время алгоритма заметно увеличивается.
  
 
=== Детерминированность ===
 
=== Детерминированность ===

Версия 16:17, 12 июня 2012

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

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

Так как данные могут хранится в разных структурах, то и алгоритмы для каждой структуры могут отличаться. Например, при хранении данных в списке, нежели чем в массиве, сортировка слиянием потребует $O(n^2)$ времени и $O(1)$ памяти против $O(n \log n)$ и $O(n)$ с использованием массива; а вот сортировка пузырьком не изменится.

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

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

Время работы

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

Память

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

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

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

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

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

Детерминированность

Алгоритм сортировки называется детерминированным, если каждая операция присваивания, обмена и т.д. не зависит от предыдущих. Все сортирующие сети являются детерминированными.

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

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


Название Лучшее время Среднее Худшее Память Стабильность Обмены (в среднем) Описание
Сортировка пузырьком
(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(\log n)$
(модифицированная реализация)
Да $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_k n)$ $O(n^2)$ $O(n)$ Да - распихиваем элементы в $k$ карманов, сортируем элементы внутри карманов, из каждого кармана данные записываются в массив в порядке разбиения.
Цифровая сортировка
(Radix Sort)
$O(n \lg n)$ $O(n \lg n)$ $O(n \lg n)$ $O(n)$ Да - сортировка, аналогичная карманной. карманы в данном случае - цифры от 0 до 9.
Сортировка подсчетом
(Counting Sort)
$O(n)$ $O(n + k)$ $O(k)$ $O(n + k)$ Да $O(n + k)$ Сортировка объектов, ключи которых входят в заранее известный диапазон целых чисел. $k$ - длина диапазона.
Сортировка Хэна
(Han's Sort)
$O(n \log \log n)$ $O(n \log \log n)$ $O(n \log \log n)$ $O(n)$ Да $O(n \log \log n)$ Очень сложная сортировка, основанная на принадлежности ключей к целым числам. использует экспоненциальное поисковое дерево Андерсона.


Ссылки

Википедия срывает покровы </wikitex>