Sortowanie bąbelkowe

Z Wikipedii, wolnej encyklopedii
Sortowanie bąbelkowe
Ilustracja
Przykład działania algorytmu sortowania bąbelkowego
Rodzaj

sortowanie

Struktura danych

tablica, lista

Złożoność
Czasowa

Pamięciowa

Wizualizacja sortowania bąbelkowego
Wizualizacja sortowania bąbelkowego

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

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 przejść, a w każdym przejściu wykonuje porównań (gdzie to numer przejścia), przez co jego teoretyczna złożoność czasowa wynosi 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 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.

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]