Метод бульбашки

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

Алгоритм В.

Задано масив елементів R₁,R₂,…,R_n.

Даний алгоритм реорганізує масив у висхідному порядку, тобто для його елементів буде мати місце співвідношення R_i < R_j - для всіх i,j=1..n_.

В1. Цикл за індексом проходження. Повторювати кроки В2 і В3 при i=1..n-1.

В2. Ініціалізація прапорця перестановки: встановити Fl=0.,

В3. Виконання проходження. Повторювати при j=1,2,…,n-i: якщо R_j+1 <R_j, то встановити Flg=1 та переставити місцями елементи R_j<->R_{j+1 ,} ; якщо Fl=0, то завершити виконання алгоритму.

В4. Кінець. Вихід.

Робота алгоритму Вочевидна. Перед кожним проходженням змінна Fl приймає значення нуль. Її значення аналізується в кінці кожного кроку. Якщо воно не змінилося, сортування виконане повністю. Характеристика сортування бульбашкою в гіршому випадку складає 1/2n(n-1) порівнянь і 1/2n(n-1) перестановок. Середня кількість проходжень приблизно дорівнює величині 1 ,25nÖ n. Наприклад, якщо n=10, потрібно виконати шість проходжень послідовності.

Середня кількість порівнянь і перестановок також пропорційна величині n². Отже складність алгоритму сортування бульбашкою становить О( n² ). Цей метод неефективний для масивів великого розміру. Існує багато модифікацій даного алгоритму.