Sortowanie bąbelkowe

Autor podstrony: Krzysztof Zajączkowski

Stronę tą wyświetlono już: 5726 razy

Najprostsza wersja tego algorytmu umożliwia sortowanie danych w n² krokach, gdzie n oznacza liczbę elementów sortowanych. Można zredukować liczbę niezbędnych kroków wiedząc, że po każdym przejściu na pozycji i ≥ n - k znajdują się maksymalne wartości już posortowane. Przy czym k określa numer kolejnego przejścia przez tablicę sortowanych wartości. Zasada działania algorytmu jest następująca:

zaczynając od elementu 0 a kończąc na elemencie n - k sprawdzam czy a_i > a_{i + 1}, jeżeli tak to zamieniam je miejscami;
dopóki n - k > 1 lub w danym przejściu nie wykonano żadnej zamiany wartości wykonuj kolejne przejście z punktu 1

Zasadę działania tego algorytmu można zobaczyć na poniższej animacji wykonanej z wykorzystaniem dynamicznie tworzonego wykresu słupkowego z strony Programowanie → Projekty JavaScript → Skrypt JavaScript tworzący wykres słupkowy w formacie SVG.

Rys. 1

Animacja algorytmu sortowania bąbelkowego. Kolory użyte w animacji oznaczają:

czerwony - elementy tablicy, których wartości są zamieniane miejscami;
niebieski - elementy tablicy, których wartości zostały porównane i nie są zamieniane miejscami;
zielony - pozostałe elementy tablicy;

W najgorszym przypadku liczba kroków niezbędnych do wykonania w implementacji z powyższej animacji wynosi: