Порівнюйте алгоритми сортування у реальному часі: швидке сортування, злитне, бульбашкове, вставками. Кожне порівняння супроводжується звуком і кольором — відчуйте різницю між O(n²) і O(n log n).
Алгоритми O(n²) (бульбашкове, вибіркове) роблять O(n²) порівнянь і різко сповільнюються зі збільшенням n. Алгоритми O(n log n) (швидке, злитне) масштабуються значно краще на великих масивах.
Виберіть алгоритм та розмір масиву. Виберіть тип початкового розташування (випадковий, перевернутий, майже відсортований). Натисніть «Сортувати». Порівняйте кількість порівнянь і прокруток.
Timsort — гібрид злитного сортування та вставками — є стандартним алгоритмом сортування у Python (з 2002 р.) і Java (з 2009 р.). Він оптимізований для реальних даних, що часто містять уже впорядковані ділянки.
Ця симуляція анімує дванадцять класичних алгоритмів сортування у вигляді ряду вертикальних стовпчиків, висота яких відповідає значенням, що впорядковуються. Під час роботи алгоритму стовпчики, які порівнюються, обмінюються місцями, перезаписуються або позначені як опорний елемент, підсвічуються різними кольорами, а осцилятор Web Audio перетворює висоту кожного стовпчика на тон у діапазоні від 120 Гц до 1600 Гц — тож ви буквально чуєте, як масив стає впорядкованим. Лічильники в реальному часі відстежують кількість порівнянь, обмінів, звернень до масиву та витрачений час, дозволяючи виміряти реальну вартість кожного методу.
Сортування — одна з найбільш досліджених задач інформатики, адже майже кожна серйозна програма покладається на впорядковані дані: для бінарного пошуку, усунення дублікатів, індексації баз даних, рендерингу тощо. Представлені алгоритми охоплюють основні родини підходів: прості квадратичні методи (бульбашкове, вставками, вибіркою), методи «розділяй і володарюй» (злиттям, швидке), вибірку на основі купи (пірамідальне сортування) та непорівняльні цілочисельні сортування (підрахунком, порозрядне). Фундаментальний результат 1972 року довів, що жодне сортування на основі порівнянь не може в середньому побити O(n log n) порівнянь — саме тому сортування злиттям, швидке та пірамідальне домінують у бібліотеках загального призначення.
Що означають кольори стовпчиків?
Сині стовпчики — невпорядковані елементи, помаранчевий позначає елементи, що зараз порівнюються, червоний — обмін місцями в процесі, фіолетовий — опорний або ключовий елемент, блакитний (cyan) — перезапис (використовується у злитному, підрахунковому та порозрядному сортуванні), а зелені стовпчики підтверджено перебувають на своєму фінальному відсортованому місці.
Чому я чую, як відбувається сортування?
Щоразу, коли алгоритм торкається стовпчика, відтворюється короткий тон трикутної хвилі, частота якого логарифмічно відповідає значенню цього стовпчика. Низькі стовпчики звучать глибоко, а високі — пронизливо, тож відсортований масив утворює плавну висхідну гаму — звукову ознаку того, як порядок виникає з хаосу.
Який алгоритм найшвидший?
Для випадкових даних швидке сортування, сортування злиттям та пірамідальне сортування (усі в середньому O(n log n)) значно швидші за квадратичні методи O(n²), такі як бульбашкове чи вибіркою. Для цілочисельних ключів у невеликому діапазоні непорівняльні сортування (підрахунком — O(n+k), порозрядне — O(nk)) можуть бути ще швидшими, оскільки вони обходять нижню межу O(n log n) для порівняльних сортувань.
Швидке сортування в середньому має складність O(n log n), але в найгіршому випадку деградує до O(n²) — зазвичай коли опорний елемент раз у раз виявляється найменшим або найбільшим, що може статися на вже відсортованих або спеціально підібраних вхідних даних. Реальні реалізації пом'якшують це за допомогою випадкового вибору опорного елемента або методу «медіана трьох».
Сортування злиттям завжди виконується за O(n log n) незалежно від вхідних даних і є стабільним, але потребує O(n) додаткової пам'яті для злиття підмасивів. Швидке сортування працює на місці, використовуючи менше пам'яті, і зазвичай швидше на практиці завдяки кращій поведінці кешу, але воно нестабільне і має той самий найгірший випадок O(n²).
Вони не засновані на порівняннях. Підрахункове сортування підраховує, скільки разів зустрічається кожне значення, і безпосередньо відновлює масив, працюючи за O(n+k), де k — діапазон значень. Порозрядне сортування обробляє числа розряд за розрядом за допомогою стабільного розподілу по «кошиках». Оскільки вони ніколи не порівнюють два елементи між собою, нижня межа для порівняльних сортувань на них не поширюється.
Стабільне сортування зберігає відносний порядок елементів, які вважаються рівними. Це важливо під час сортування записів за кількома ключами — наприклад, сортування за іменем, а потім стабільно за датою, зберігає записи з однаковою датою в алфавітному порядку. Сортування злиттям, вставками та підрахункове є стабільними; швидке, пірамідальне та вибіркою — зазвичай ні.
Квадратичні сортування, такі як бульбашкове, гноміче та шейкерне (cocktail), рідко використовуються у промислових продуктах, але є чудовими навчальними інструментами: їхня проста логіка робить механізм «порівняння-обмін» очевидним, а спостереження за тим, як вони повільно повзуть крізь великий масив, дає інтуїтивне відчуття того, чому важлива алгоритмічна складність.
Так. На дуже малих масивах накладні витрати «розумних» алгоритмів через константний множник можуть зробити прості методи, такі як сортування вставками, конкурентоспроможними — саме тому багато реальних бібліотек перемикаються на сортування вставками нижче певного порогу. Зі зростанням масиву методи O(n log n) рішуче вириваються вперед, і розрив стрімко збільшується.
Так, базові ідеї ідентичні. Більшість стандартних бібліотек мов програмування використовують гібридні сортування — наприклад, Timsort (гібрид злиття та вставок) у Python і в сортуванні об'єктів Java, а також introsort (швидке сортування, що переходить на пірамідальне) у C++. Цей візуалізатор показує підручникові будівельні блоки, з яких складаються ці промислові сортування.