Sortowanie bąbelkowe
Ten artykuł od 2012-11 wymaga zweryfikowania podanych informacji. |
![]() Przykład działania algorytmu sortowania bąbelkowego | |
Rodzaj | |
---|---|
Struktura danych | |
Złożoność | |
Czasowa |
|
Pamięciowa |
|
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]
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