234
правки
Изменения
Нет описания правки
<wikitex>
''Сортировкой'' называется процесс упорядочивания множества объектов по какому-либо признаку.
Обычно таким признаком служит лексикографический номер.
Так как данные могут хранится в разных структурах, то и алгоритмы для каждой структуры могут отличаться. Например, при хранении данных в списке, нежели чем в массиве, сортировка слиянием потребует $O(n^2)$ времени и $O(1)$ памяти против $O(n \log n)$ и $O(n)$ с использованием массива; а вот сортировка пузырьком не изменится.
Также есть алгоритмы параллельной сортировки данных (т.н. [[Сортирующие сети]]), время работу которых $O(\log n)$.
== Классификация сортировок ==
=== Время работы. ===
Важный параметр, когда объекты имеют большой размер. В таком случае при большом кол-ве обменов время алгоритма заметно увеличивается.
=== Детерминированность ===
Алгоритм сортировки называется ''детерминированным'', если каждая операция присваивания, обмена и т.д. не зависит от предыдущих.
Все сортирующие сети являются детерминированными.
== Сравнение сортировок ==
Будем рассматривать сортировки массива из $n$ элементов множества $A$,
причем на $A$ должно быть выполнено [[Бинарное отношение|отношение эквивалентности]].
{|class="wikitable"
