Sortowanie bąbelkowe, algorytm klasy O(N2)

Algorytm sortowania "bąbelkowego" jest jednym z najprostszych algorytmów służących do sortowania liczb, o złożoności czasowej O(N2) i pamięciowej O(1).

Jego nazwa wzięła się od "pęcherzyków powietrza", które ulatywały w górę tuby wypełnionej wodą. Jeżeli tablicę danych potraktujemy jak pojemnik z wodą, a zawarte w niej dane jako pęcherzyki powietrza, to najszybciej do góry będą lecieć najlżejsze czyli liczby o najmniejszej wartości.

Algorytm ten opiera się na zasadzie "maximum". To znaczy, że każda liczba jest mniejsza lub równa w stosunku do liczby maksymalnej. Kiedy będziemy porównywać kolejno liczby, to możemy wyznaczyć największą z nich. Następnie pozostałe dane możemy skrócić o znalezioną wcześniej cyfrę i po raz kolejny szukać największej liczby. Ten element będziemy powtarzać do momentu kiedy zostanie nam tylko jedna liczba. Dzięki czemu ciąg liczb będzie uporządkowany.

Kod będzie wykonywał n przejść, a w każdym przejściu n-1 porównań. Więc jego teoretyczna złożoność czasowa będzie wynosić O(n2).

Przykład działania

Załóżmy, że mamy ciąg wejściowy [4,2,5,1,7], a każdy kolejny wiersz znajdujący się na poniższej ilustracji symbolizuje wypchnięcie największego elementu na koniec:

Niebieski fragment, oznacza posortowane liczby

Niebieski fragment, oznacza posortowane liczby. Fot: Wikipedia.

Przykładowy program wykorzystujący algorytm sortowania bąbelkowego (napisany w języku Pascal):

,