Пірамідальне сортування
Складає зі списку купу, тобто дерево, де кожен батько більший за своїх дітей. Потім раз за разом переносить найбільше значення в кінець.
- Ω(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, а найбільше значення завжди на початку. Обміном переносимо його в кінець, зменшуємо купу на одне значення і відновлюємо її. Відсортована частина росте справа.
Коли варто використовувати
Коли швидкість має лишатися доброю навіть у найгіршому випадку, а додаткової пам'яті немає, наприклад на малих пристроях. У середньому воно повільніше за швидке сортування, тому його часто тримають як запасний варіант.