2015-10-13
463
Другим добре відомим методом із класу вибірки є метод, що ґрунтується на ідеї спливаючої бульбашки. На відміну від попереднього в даному алгоритмі два елементи обмінюються місцями, як тільки виявлено, що між ними порушений порядок.
Алгоритм В.
Задано масив елементів R1,R2,…,Rn.
Даний алгоритм реорганізує масив у висхідному порядку, тобто для його елементів буде мати місце співвідношення Ri < Rj - для всіх i,j=1..n.
В1. Цикл за індексом проходження. Повторювати кроки В2 і В3 при i=1..n-1.
В2. Ініціалізація прапорця перестановки: встановити Fl=0.,
В3. Виконання проходження. Повторювати при j=1,2,…,n-i: якщо Rj+1 <Rj, то встановити Flg=1 та переставити місцями елементи Rj<->Rj+1 , ; якщо Fl=0, то завершити виконання алгоритму.
В4. Кінець. Вихід.
Робота алгоритму Вочевидна. Перед кожним проходженням змінна Fl приймає значення нуль. Її значення аналізується в кінці кожного кроку. Якщо воно не змінилося, сортування виконане повністю. Характеристика сортування бульбашкою в гіршому випадку складає 1/2n(n-1) порівнянь і 1/2n(n-1) перестановок. Середня кількість проходжень приблизно дорівнює величині 1 ,25nÖ n. Наприклад, якщо n=10, потрібно виконати шість проходжень послідовності.
Середня кількість порівнянь і перестановок також пропорційна величині n2. Отже складність алгоритму сортування бульбашкою становить О( n2 ). Цей метод неефективний для масивів великого розміру. Існує багато модифікацій даного алгоритму.
