| Sortowanie bąbelkowe |
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(n2) 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
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
Algorytm wykonuje n przejść a każdym przejściu wykonuje n-1 porównań. Przez co jego teoretyczna złożoność czasowa wynosi O(n2). Niestety w podstawowej wersji algorytmu nie można tego czasu polepszyć. Mało tego, każda permutacja powoduje, że algorytm jest wykonywany w czasie pesymistycznym.
Modyfikacje powodujące ulepszenie czasu
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 zmiane jest podnoszona. A po wykonaniu przejścia jest 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ętle (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
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.
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-2 do for j=r-1 downto i+1 do if (tab[j-1]>tab[j]) zamień elementy tab[j] i tab[j-1]
Implementacja
Zobacz też
Nie znaleziono szukanej frazy! Poniżej znajduje się fraza najbardziej przypominająca szukaną.
![[\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}]](http://upload.wikimedia.org/math/2/c/3/2c385d560afc522b8eaf5a97b2554829.png)
![[\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}]](http://upload.wikimedia.org/math/6/c/f/6cf90b8e431cad9744d1f0606d3493a5.png)
![[\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}]](http://upload.wikimedia.org/math/9/d/1/9d140fe75fdd107393c458dda41e30ea.png)
![[\underbrace{\color{OliveGreen}1,2}_{1 < 2},{\color{Blue}4},{\color{Blue}5},{\color{Blue}7}]](http://upload.wikimedia.org/math/2/7/4/27434a5558f662fb054ceb1a7f72261b.png)
