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