Sortowanie bąbelkowe

Z Wikipedii

Przykład działania algorytmu sortowania bąbelkowego.

Sortowanie bąbelkowe (ang. bubble sort) - prosta metoda sortowania o złożoności czasowej O(n²) i pamięciowej O(1).

Polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona porządek, w jakim się sortuje tablicę. Sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano żadnej zmiany.

[edytuj] Przykład działania

Ciąg wejściowy: |4|2|5|1|7|, ^-^ wskazuje aktualnie porównywane komórki. Każdy wiersz symbolizuje wypchnięcie kolejnego największego elementu na koniec ("wypłynięcie największego bąbelka").

|4|2|5|1|7| -> |2|4|5|1|7| -> |2|4|5|1|7| -> |2|4|1|5|7|
 ^-^              ^-^              ^-^              ^-^
|2|4|1|5|7| -> |2|4|1|5|7| -> |2|1|4|5|7|
 ^-^              ^-^              ^-^
|2|1|4|5|7| -> |1|2|4|5|7|
 ^-^              ^-^
|1|2|4|5|7|
 ^-^

Zobacz w Wikiźródłach Sortowanie bąbelkowe

[edytuj] Pseudokod

Pseudokod algorytmu dla tablicy o rozmiarze "r" (elementy tablicy są numerowane od 0 do r-1):

sortuj(tablica tab)
   for i=0 to r-1 do
        for j=r-1 downto i+1 do
             if (tab[j-1]>tab[j])
                  zamień elementy tab[j] i tab[j-1]