Sortowanie bąbelkowe

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Sortowanie bąbelkowe
Bubble sort animation.gif
Przykład działania algorytmu sortowania bąbelkowego.
Rodzaj Sortowanie
Struktura danych Tablica, lista
Złożoność
Czasowa О(n²)
Pamięciowa O(1)

Sortowanie bąbelkowe (ang. bubble sort) - prosta metoda sortowania o złożoności czasowej O(n^2) 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.

Dowód matematyczny[edytuj | edytuj kod]

Algorytm opiera się na zasadzie maksimum, tj. każda liczba jest mniejsza lub równa od liczby maksymalnej. Porównując kolejno liczby można wyznaczyć największą z nich. Następnie ciąg częściowo posortowany (mający liczbę maksymalną), można skrócić o tę liczbę i ponowić szukanie maksimum, już bez elementów odrzuconych i tak długo, aż zostanie nam jeden element. Otrzymane kolejne maksima są coraz mniejsze przez co ciąg jest uporządkowany.

Złożoność obliczeniowa[edytuj | edytuj kod]

Przykład działania

Algorytm wykonuje n-1 przejść, a w każdym przejściu wykonuje n-k porównań (gdzie k=1,2..n-1 to numer przejścia), przez co jego teoretyczna złożoność czasowa wynosi O(n^2). W podstawowej wersji algorytmu nie można tego czasu skrócić, a każda permutacja powoduje, że algorytm jest wykonywany w czasie pesymistycznym.

Modyfikacje powodujące ulepszenie czasu[edytuj | edytuj kod]

Algorytm można rozbudować tak, by czas optymistyczny był lepszy. Najłatwiejsze jest dodanie flagi informującej, czy w danej iteracji doszło do zmiany. Flaga jest zerowana na wejściu w przebiegu pętli, w przypadku natrafienia na zmianę jest podnoszona, a po wykonaniu przejścia sprawdzana. Jeśli nie było zmian, to sortowanie jest zakończone. Modyfikacja ta wprawdzie wydłuża czas wykonania jednego przejścia przez pętlę (gdyż trzeba wyzerować flagę, podnieść ją i sprawdzić), jednakże w wariancie optymistycznym (ciąg częściowo posortowany) może zaoszczędzić iteracji, przez co algorytm będzie działać szybciej.

Przykład działania[edytuj | edytuj kod]

Ciąg wejściowy [4, 2, 5, 1, 7]. Każdy wiersz symbolizuje wypchnięcie kolejnego największego elementu na koniec ("wypłynięcie największego bąbelka"). Niebieskim kolorem oznaczono końcówkę ciągu już posortowanego.


[\underbrace{\color{Red}4,2}_{4 > 2},5,1,7] \rightarrow
[2,\underbrace{\color{OliveGreen}4,5}_{4 < 5},1,7] \rightarrow
[2,4,\underbrace{\color{Red}5,1}_{5 > 1},7] \rightarrow
[2,4,1,\underbrace{\color{OliveGreen}5,7}_{5 < 7}]

[\underbrace{\color{OliveGreen}2,4}_{2 < 4},1,5,{\color{Blue}7}] \rightarrow
[2,\underbrace{\color{Red}4,1}_{4 > 1},5,{\color{Blue}7}] \rightarrow
[2,1,\underbrace{\color{OliveGreen}4,5}_{4 < 5},{\color{Blue}7}]

[\underbrace{\color{Red}2,1}_{2 > 1},4,{\color{Blue}5},{\color{Blue}7}] \rightarrow
[1,\underbrace{\color{OliveGreen}2,4}_{2 < 4},{\color{Blue}5},{\color{Blue}7}]

[\underbrace{\color{OliveGreen}1,2}_{1 < 2},{\color{Blue}4},{\color{Blue}5},{\color{Blue}7}]

Pseudokod[edytuj | edytuj kod]

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

procedure bubbleSort( A : lista elementów do posortowania )
  n = liczba_elementów(A)
   do
    for (i = 0; i < n-1; i++) do:
      if A[i] > A[i+1] then
        swap(A[i], A[i+1])
      end if
    end for
    n = n-1
  while n > 1
end procedure

Implementacja[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]