Sortowanie bąbelkowe

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

Najprostsza wersja tego algorytmu umożliwia sortowanie danych w n2 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 in - 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:

  1. zaczynając od elementu 0 a kończąc na elemencie n - k sprawdzam czy ai > ai + 1, jeżeli tak to zamieniam je miejscami;
  2. 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 bombelkowego. 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:

złożoność obliczeniowa implementacji algorytmu sortowania bombelkowego [1]

Zapis wyrażenia w formacie TeX-a:

\frac{1}{2}\cdot n\cdot (n-1)

Komentarze