Візуалізуйте та порівнюйте 6 алгоритмів сортування поруч. Спостерігайте за бульбашковим, вставкою, вибором, злиттям, швидким та пірамідальним сортуванням з анімацією стовпців. Побачте O(n²) проти O(n log n) у дії.
Бульбашкове O(n²): багаторазово обмінює сусідні елементи. Вставкою O(n²): вставляє кожен елемент на правильне місце. Вибором O(n²): знаходить мінімум і ставить його. Злиттям O(n log n): поділ і злиття — стабільний. Швидке O(n log n) середн.: розбиття за опорним елементом. Пірамідальне O(n log n): використовує структуру купи.
Сортування вставкою чудово працює на майже відсортованих даних: O(n) у кращому випадку. Швидке сортування деградує до O(n²) на вже відсортованих масивах з наївним опорним. Злиттям та пірамідальне завжди O(n log n).
Реальні бібліотеки (Timsort у Python/Java) поєднують вставкою для малих масивів зі злиттям для великих. Кеш-локальність важлива: швидке сортування часто перевершує злиття попри однаковий O-нотацію завдяки послідовному доступу до пам'яті.
Цей візуалізатор одночасно запускає шість класичних алгоритмів сортування на однаковому початковому масиві, тож можна побачити, як Бульбашкове, Вставкою, Вибором, Злиттям, Швидке та Пірамідальне сортування "змагаються" в реальному часі. Кожен canvas перемальовує висоту стовпців кадр за кадром на основі JS-генератора, підсвічуючи два індекси, що порівнюються (жовтий) чи міняються місцями (червоний), а відсортовані ділянки стають зеленими. Це наочний спосіб побачити, чому алгоритми O(n log n) обганяють O(n²) зі збільшенням розміру масиву.
Шість canvas-полотен працюють незалежно через JS-генератори (yield), що призупиняються після кожного порівняння, дозволяючи всім шести алгоритмам анімуватись синхронно крок за кроком. Висота стовпця — це значення, колір — роль: жовтий = порівнюється, червоний = обмін, зелений = завершено.
Налаштуйте повзунки Розмір масиву (10-80) і Швидкість (1-30 кроків за кадр), оберіть початковий стан кнопками Випадковий / Майже відсортований / Зворотний / Всі однакові, потім натисніть Сортувати все, щоб побачити перегони, або Новий масив, щоб перемішати.
На майже відсортованому масиві сортування вставкою може завершитись майже за O(n) — на практиці швидше за "кращі" алгоритми O(n log n) для малих, майже впорядкованих вхідних даних, тому реальні бібліотеки на кшталт Timsort саме на нього й перемикаються.
Вони належать до класу складності O(n log n), який зростає значно повільніше за клас O(n²) (Бульбашкове, Вставкою, Вибором) зі збільшенням масиву. При стандартному масиві з 40 елементів різниця вже помітна; збільшіть Розмір масиву до 80 — і вона стане разючою.
Ця реалізація завжди обирає останній елемент опорним. На вже відсортованому чи зворотному масиві такий вибір є найгіршим випадком для швидкого сортування, наближаючи його до O(n²) замість середнього O(n log n) — відома слабкість, яку на практиці усувають випадковим чи медіанним опорним елементом.
Лічильники "Порівнянь (Бульбашкове)" і "Порівнянь (Злиттям)" підраховують кожне порівняння елементів (змінна c у кожному генераторі), дозволяючи порівнювати алгоритмічну вартість, а не лише візуальну швидкість.
Він починає з повністю відсортованого масиву від 1 до n, а потім виконує приблизно n/10 випадкових обмінів, симулюючи дані, які здебільшого впорядковані — сценарій, де Вставкою та Бульбашкове показують найкращий результат, близький до O(n).
Так — воно завжди ділить масив навпіл і зливає частини незалежно від порядку вхідних даних, тож його час роботи не залежить від того, наскільки дані вже відсортовані, на відміну від Швидкого чи сортування Вставкою, чия швидкість змінюється залежно від порядку вхідних даних.