Пирамидальная сортировка
Превращает список в кучу, то есть дерево, где каждый родитель больше своих детей. Затем раз за разом переносит наибольшее значение в конец.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(1)
- нет
- да
Лучший случай: как растёт время с размером списка n, когда входные данные самые удобные для алгоритма.
Средний случай: обычный рост времени с n. При n² вдвое больше значений сортируются вчетверо дольше; n log n растёт намного медленнее.
Худший случай: рост времени на самых неудобных данных. Важно, когда скорость не должна падать никогда.
Память: сколько памяти нужно сверх самого списка. 1 значит несколько переменных, n значит копию списка.
Стабильное: равные значения сохраняют исходный порядок. Это важно, когда записи сортируют по одному полю.
Без дополнительной памяти: сортирует внутри самого списка, без второго списка.
- сравнение
- перемещение
- на окончательном месте
Нажмите «Воспроизвести»: линии покажут, как растут затраты
Нажмите «Воспроизвести» или проходите алгоритм по шагам.
Пробел: воспроизведение или пауза. Стрелки влево и вправо: шаг. Home и End: в начало или в конец.
Попробуйте: Выберите обратный список. Куча строится почти без обменов, а потом каждый раз наибольшее значение уходит в конец.
Как это работает
Куча хранится прямо в списке: дети значения на позиции i стоят на позициях 2i+1 и 2i+2, а наибольшее значение всегда в начале. Обменом переносим его в конец, уменьшаем кучу на одно значение и восстанавливаем её. Отсортированная часть растёт справа.
Когда стоит применять
Когда скорость должна оставаться хорошей даже в худшем случае, а лишней памяти нет, например на маленьких устройствах. В среднем она медленнее быстрой сортировки, поэтому её часто держат как запасной вариант.