Алгоритми в дії
Алгоритми в дії — безкоштовна інтерактивна симуляція зі StudyFi Lab. Працює просто в браузері, без реєстрації та встановлення.
Сортування і пошук крок за кроком
Експерименти
Сортування бульбашкою
Сортування бульбашкою порівнює сусідні елементи й міняє їх місцями, якщо вони стоять у неправильному порядку. Після кожного проходу найбільший елемент «спливає» в кінець, і невпорядкована частина коротшає. Якщо за прохід не було жодного обміну, масив упорядкований. У найгіршому випадку потрібно n(n−1)/2 порівнянь, тобто O(n²).
Спробуй: Вибери зворотний порядок і порівняй кількість порівнянь з n(n−1)/2. Потім спробуй майже впорядкований масив — він завершиться за кілька проходів.
Сортування вставками
Сортування вставками схоже на впорядкування карт у руці: ліва частина вже впорядкована, а кожен наступний елемент (key) зсувається ліворуч, доки не зустріне менший. Більші елементи при цьому зсуваються на одне місце праворуч. На випадкових даних це O(n²), а на майже впорядкованих — майже O(n): упорядкованому масиву потрібно лише n−1 порівнянь.
Спробуй: Запусти його на майже впорядкованому масиві, а потім на зворотному. У скільки разів більше зсувів потрібно зворотному?
Сортування злиттям
Сортування злиттям ділить масив навпіл, упорядковує кожну половину тим самим способом (рекурсія), а потім зливає дві впорядковані половини: завжди бере менший із двох перших елементів. Ділення навпіл дає log₂ n рівнів, і на кожному рівні обробляються всі n елементів, тому час завжди O(n log n). У разі рівності береться лівий елемент, тому сортування стійке.
Спробуй: Спробуй зворотний, а потім майже впорядкований масив того самого розміру. Кількість порівнянь майже не змінюється — порядок вхідних даних майже не важливий.
Швидке сортування
Швидке сортування вибирає опорний елемент — тут останній елемент відрізка (розбиття Ломуто) — і переставляє відрізок так, щоб менші елементи опинилися ліворуч, а решта праворуч. Опорний елемент стає на своє остаточне місце, а обидві частини впорядковуються так само. У середньому це O(n log n), але якщо опорний елемент ділить погано (наприклад, на вже впорядкованому чи зворотному масиві), час падає до O(n²).
Спробуй: Порівняй випадковий вхід зі зворотним. На зворотному масиві опорний елемент завжди найбільший або найменший — подивись, як підскочить кількість порівнянь.
Лінійний і двійковий пошук
Лінійний пошук перевіряє елементи по одному, тому в найгіршому випадку йому потрібно n кроків — O(n). Двійковий пошук працює лише на впорядкованому масиві: він дивиться в середину і за результатом відкидає цілу половину. Після кожного кроку лишається не більше половини, тому вистачає не більше ⌈log₂(n+1)⌉ кроків — O(log n). Для 40 елементів це 6 кроків замість 40.
Спробуй: Задай 40 елементів і шукай останнє значення. Потім вибери число, якого немає в масиві, — скільки кроків потрібно кожному пошуку, щоб це з’ясувати?
Перегони сортувань
Усі чотири алгоритми впорядковують однакові дані, і на кожній доріжці один крок — це одне порівняння або одне переміщення. Алгоритми O(n²) (бульбашкою та вставками) зростають із розміром масиву набагато швидше, ніж O(n log n) (злиттям і швидке). Але порядок залежить і від входу: на майже впорядкованому масиві часто перемагає сортування вставками.
Спробуй: Запусти перегони на випадковому масиві з 40 елементів, потім перемкнися на майже впорядкований. Чи зміниться переможець?
Поширені запитання
Що таке «Алгоритми в дії»?
Алгоритми в дії — безкоштовна інтерактивна симуляція зі StudyFi Lab. Працює просто в браузері, без реєстрації та встановлення. Сортування і пошук крок за кроком
Застосунок «Алгоритми в дії» безкоштовний?
Так. Застосунок «Алгоритми в дії» повністю безкоштовний. Він працює в браузері на комп’ютері, планшеті й телефоні, акаунт не потрібен.
Що можна дослідити в застосунку «Алгоритми в дії»?
Сортування бульбашкою, Сортування вставками, Сортування злиттям, Швидке сортування, Лінійний і двійковий пошук, Перегони сортувань.
Що показує експеримент «Сортування бульбашкою»?
Сортування бульбашкою порівнює сусідні елементи й міняє їх місцями, якщо вони стоять у неправильному порядку. Після кожного проходу найбільший елемент «спливає» в кінець, і невпорядкована частина коротшає. Якщо за прохід не було жодного обміну, масив упорядкований. У найгіршому випадку потрібно n(n−1)/2 порівнянь, тобто O(n²).
Що показує експеримент «Сортування вставками»?
Сортування вставками схоже на впорядкування карт у руці: ліва частина вже впорядкована, а кожен наступний елемент (key) зсувається ліворуч, доки не зустріне менший. Більші елементи при цьому зсуваються на одне місце праворуч. На випадкових даних це O(n²), а на майже впорядкованих — майже O(n): упорядкованому масиву потрібно лише n−1 порівнянь.
Готуєшся до контрольної?
Завантаж свої конспекти, і StudyFi перетворить їх на картки, тести й подкасти.