📊 Алгоритми Сортування — Візуалізація та Звук

Сині стовпці — невпорядковані, помаранчевий позначає елементи, які наразі порівнюють, червоний — обмін у процесі, фіолетовий — опорний або ключовий елемент, блакитний — перезапис (використовується сортуванням злиттям, підрахунком і порозрядним), а зелені стовпці підтверджено перебувають на своєму остаточному відсортованому місці.

Щоразу, коли алгоритм торкається стовпця, відтворюється короткий тон трикутної хвилі, частота якого логарифмічно відображає значення цього стовпця. Низькі стовпці звучать глибоко, а високі — високо, тож відсортований масив утворює плавну висхідну гаму — чутний слід порядку, що виникає з хаосу.

Для випадкових даних швидке сортування, сортування злиттям і пірамідальне сортування (усі в середньому O(n log 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 — діапазон значень. Порозрядне сортування обробляє числа розряд за розрядом, використовуючи стабільний прохід кошиками. Оскільки вони ніколи не порівнюють два елементи один з одним, нижня межа порівняння до них не застосовується.

Стабільне сортування зберігає відносний порядок елементів, які порівнюються рівними. Це важливо під час сортування записів за кількома ключами — наприклад, сортування за іменем, а потім стабільно за датою залишає записи з однаковою датою впорядкованими за алфавітом. Сортування злиттям, вставками та підрахункове є стабільними; швидке, пірамідальне та вибором зазвичай ні.

Квадратичні сортування, як-от бульбашкове, гномове та шейкерне, рідко застосовують у виробництві, але вони чудові навчальні інструменти: їхня проста логіка робить механізм порівняння й обміну очевидним, а спостереження за тим, як вони повзуть крізь великий масив, дає інтуїтивне відчуття того, чому важлива алгоритмічна складність.

Так. На дуже малих масивах накладні витрати хитромудрих алгоритмів можуть зробити прості методи, як-от сортування вставками, конкурентоспроможними — саме тому багато реальних бібліотек переходять на сортування вставками нижче певного порогу. У міру зростання масиву методи O(n log n) вирвуться вперед, і розрив стрімко збільшується.

Так, основні ідеї ідентичні. Більшість стандартних бібліотек мов використовують гібридні сортування — наприклад, Timsort (гібрид злиття та вставок) у Python і сортуванні об'єктів Java, та introsort (швидке сортування, що переходить на пірамідальне) у C++. Цей візуалізатор показує підручникові будівельні блоки, з яких складені ці виробничі сортування.