Візуалізатор алгоритмів сортування
Оберіть алгоритм, перемішайте масив і дивіться, як він сортується. Лічильники покажуть, скільки порівнянь і обмінів потрібно.
Що таке сортування
Сортування — впорядкування елементів за зростанням або спаданням. Це одна з найважливіших задач інформатики: впорядковані дані легше шукати, порівнювати й аналізувати.
Прості алгоритми (бульбашка, вибір, вставки) роблять порядку n² операцій: коли елементів у 10 разів більше, роботи у 100 разів більше. Швидке сортування в середньому потребує порядку n·log n порівнянь.
Що спробувати
Збільшіть кількість елементів і порівняйте таблицю «Змагання»: різниця між простими алгоритмами та швидким сортуванням швидко зростає.
Спостерігайте за бульбашковим сортуванням: після першого проходу найбільший елемент уже в кінці. Вставки працюють особливо швидко, коли масив майже впорядкований.
Приклади
- Бульбашка на 25 елементах — відкрити з цими значеннями
- Швидке сортування на 60 елементах — відкрити з цими значеннями
- Сортування вибором на 15 елементах — відкрити з цими значеннями
Часті запитання
Який алгоритм сортування найшвидший?
Для великих масивів швидке сортування та злиття (O(n log n)). Для маленьких або майже впорядкованих масивів добре працюють вставки.
Чому сортування бульбашкою повільне?
Воно порівнює сусідні елементи й переносить їх на одну позицію за раз, тому для n елементів виконує порядку n² порівнянь.
Що означає O(n²)?
Це оцінка швидкості зростання кількості операцій: якщо розмір даних збільшити вдвічі, роботи стане вчетверо більше.
Читайте також: Теорія: алгоритми та блок-схеми.