42
правки
Изменения
Нет описания правки
''Сортировкой'' называется процесс упорядочивания множества объектов по какому-либо признаку.
Также есть алгоритмы параллельной сортировки данных (т.н. [[Сортирующие сети]]), время работы которых в лучшем случае $O(\log n)$.
Параметр сортировки, показывающий, сколько '''дополнительной''' памяти требуется алгоритму. Сюда входят и дополнительный массив, и переменные, и затраты на стек вызовов. Обычно затраты бывают $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)]]
|Алгоритм состоит в разделении массива пополам, сортировки половин и их слиянии.
|- align = "center"
|[[Сортировка кучей|Пирамидальная сортировка Сортировка кучей <br>(Heap Sort)]]
|$O(n \log n)$
|$O(n \log n)$
== Ссылки ==
[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 Википедия срывает покровы- Алгоритмы сортировки]
</wikitex>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
