Швидке сортування
Швидке сортування — інтерактивний експеримент із застосунку «Алгоритми в дії», безкоштовної симуляції StudyFi Lab, яка працює просто в браузері.
Швидке сортування вибирає опорний елемент — тут останній елемент відрізка (розбиття Ломуто) — і переставляє відрізок так, щоб менші елементи опинилися ліворуч, а решта праворуч. Опорний елемент стає на своє остаточне місце, а обидві частини впорядковуються так само. У середньому це O(n log n), але якщо опорний елемент ділить погано (наприклад, на вже впорядкованому чи зворотному масиві), час падає до O(n²).
Спробуй: Порівняй випадковий вхід зі зворотним. На зворотному масиві опорний елемент завжди найбільший або найменший — подивись, як підскочить кількість порівнянь.
Поширені запитання
Що показує експеримент «Швидке сортування»?
Швидке сортування вибирає опорний елемент — тут останній елемент відрізка (розбиття Ломуто) — і переставляє відрізок так, щоб менші елементи опинилися ліворуч, а решта праворуч. Опорний елемент стає на своє остаточне місце, а обидві частини впорядковуються так само. У середньому це O(n log n), але якщо опорний елемент ділить погано (наприклад, на вже впорядкованому чи зворотному масиві), час падає до O(n²).
Як спробувати «Швидке сортування»?
Порівняй випадковий вхід зі зворотним. На зворотному масиві опорний елемент завжди найбільший або найменший — подивись, як підскочить кількість порівнянь.
Готуєшся до контрольної?
Завантаж свої конспекти, і StudyFi перетворить їх на картки, тести й подкасти.