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