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(N²) 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(n²).

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. Fot: Wikipedia.

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

program sortowanieBabelkowe;
USES crt;
VAR
    liczby:array[1..6] of integer;
    i,j,tmp:integer;
BEGIN
    clrscr;
    {wypełniamy tablice liczbami}
    writeln('Podaj 6 liczb, które chcesz posortować:');
    for i:= 1 to 6 do
        readln(liczby[i]); {zapisujemy liczby}
    
    {sortowanie}
    for i:=1 to 5 do 
         for j:=1 to 5 do
              if liczby[j] > liczby[j+1] then
                   begin
                   tmp := liczby[j];
                   liczby[j] := liczby[j+1];
                   liczby[j+1] := tmp;
                   end;
     
     {wyświetlamy posortowane liczby}
     writeln('Posortowane liczby:');
     for i:=1 to 6 do
          writeln(liczby[i]);

     repeat until keypressed;
END.

Algorytmy, sortowanie bąbelkowe