Алгоритми. 
Загальні характеристики роботи різних методів сортування

Сортування методом бульбашки

Розташуємо масив зверху вниз, від нульового елемента — до останнього.

Ідея методу: крок сортування полягає в проході знизу вгору по масиву. По дорозі проглядаються пари сусідніх елементів. Якщо елементи деякої пари знаходяться в неправильному порядку, то міняємо їх місцями (Рис. 5.1).

Рисунок 2.1 — Принцип роботи сортування методом бульбашки.

Після нульового проходу по масиву «вгорі» виявляється самий «легкий» елемент — звідси аналогія з бульбашкою (Рис. 5.2). Наступний прохід робиться до другого зверху елемента, таким чином другий за величиною елемент піднімається на правильну позицію.

Робимо проходи по все зменшується нижній частині масиву до тих пір, поки в ній не залишиться тільки один елемент. На цьому сортування закінчується, так як послідовність упорядкована за зростанням.(Рис. 2.2).

Рисунок 2.2 — Результат нульового кроку сортування.

Середнє число порівнянь та обмінів мають квадратичний порядок зростання: Theta (n2), звідси можна зробити висновок, що алгоритм бульбашки дуже повільний і малоефективний.

Тим не менш, у нього є величезний плюс: він простий і його можна по-всякому покращувати. Чим ми зараз і займемося.

По-перше, розглянемо ситуацію, коли на якому-небудь з проходів не відбулося жодного обміну. Що це означає?

Це означає, що всі пари розташовані в правильному порядку, так що масив вже відсортований. І продовжувати процес не має сенсу (особливо, якщо масив був відсортований з самого початку!).

Отже, перше поліпшення алгоритму полягає в запам’ятовуванні, чи проводився на даному проході який-небудь обмін. Якщо ні - алгоритм закінчує роботу.

Процес поліпшення можна продовжити, якщо запам’ятовувати не тільки сам факт обміну, але і індекс останнього обміну k. Дійсно: всі пари сусіди елементів з індексами, меншими k, вже розташовані в потрібному порядку. Подальші проходи можна закінчувати на індексі k, замість того щоб рухатися до встановленої заздалегідь верхньої межі i.

Якісно інше поліпшення алгоритму можна отримати з наступного спостереження. Хоча легкий бульбашка знизу підніметься наверх за один прохід, важкі бульбашки опускаються зі мінімальною швидкістю: один крок за ітерацію. Так що масив 2 3 4 5 6 1 буде відсортований за 1 прохід, а сортування послідовності 6 1 2 3 4 5 зажадає 5 проходів.

Щоб уникнути подібного ефекту, можна змінювати напрямок наступних один за іншим проходів. Одержаний алгоритм іноді називають «шейкер-сортуванням» .

Наскільки описані зміни вплинули на ефективність методу? Середня кількість порівнянь, хоч і зменшилася, але залишається O (n2), в той час як число обмінів не помінялося взагалі ніяк. Середнє (воно ж найгірше) кількість операцій залишається квадратичним.

Додаткова пам’ять, очевидно, не потрібно. Поведінка удосконаленого (але не початкового) методу досить природне, майже відсортований масив буде відсортований набагато швидше випадкового. Сортування бульбашкою стійка, проте шейкер-сортування втрачає цю якість.

На практиці метод бульбашки, навіть з поліпшеннями, працює, на жаль, занадто повільно. А тому — майже не застосовується.