Розбираємо прості сортування. Бульбашкове сортування

Сортування бульбашкою  

Сортування бульбашкою є, мабуть, одним з найвідоміших алгоритмів сортування. Цей алгоритм досить простий та зрозумілий, дуже часто з нього починають знайомити з алгоритмами у вишах та на різноманітних курсах. Єдине питання, яке може зараз виникнути: «Чому ми не розглядали його раніше?»

А власне алгоритм працює так: 

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

Як уже зазначалося, алгоритм дуже простий, і як зазвичай буває в цьому світі, простота та ефективність алгоритмів є зворотньо пропорційними величинами. Тому обчислювальна складність цього алгоритму виглядає наступним чином:  

Найгірший час: O(n²);  

Середній час: Θ(n²);  

Кращій час: Ω(n).  

У статті про складність алгоритмів ми використали сортування бульбашкою в якості прикладу, тож докладно про те, чому складність саме така, можна прочитати там.  

Шейкерне сортування  

Шейкерне сортування являє собою двонаправлене бульбашкове сортування. У цьому випадку алгоритм обробляє масив спочатку зліва направо, переміщуючи найбільший елемент у кінець масиву, а потім справа наліво, переміщуючи найменший елемент на початок масиву. Нижче можна побачити реалізацію цього алгоритму на Java. 

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

Найгірший час: O(n²);  

Середній час: Θ(n²);  

Кращий час: Ω(n).  

Сортування гребінцем  

Алгоритм сортування гребінцем — це покращений варіант сортування бульбашкою. Відмінність полягає в тому, що порівнюються не два сусідні елементи, а два елементи розташовані на деякій відстані один від одного. Такий підхід дозволяє на початку сортування перемістити елементи з меншими значеннями з кінця масиву на його початок, за рахунок чого відбувається зменшення обчислювальної складності. Відстань між елементами, що порівнюються, обирається не випадково, а з врахуванням фактора зменшення. Оптимальним значенням цього фактору прийнято вважати число 1,247, яке обчилюється наступним чином

Отже, при першому проході алгоритму відстань між елементами, що порівнюються, буде дорівнювати розміру масиву, поділеному на 1,247, і на кожному наступному кроці відстань між елементами буде ділится на цю величину.

Такий підхід й справді дозволяє знизити обчислювальну складність алгоритму, і тут вона буде наступною:  

Найгірший час: O(n²);  

Середній час: Θ (n²/ 2p);  

Кращий час: Ω(n log(n)).  

Однак, потрібно пам’ятати, що це сортування нестійке, тобто воно може змінювати відносний порядок однакових елементів.  

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