Sortowanie bąbelkowe

Sama nazwa kojarzy nam się z bąbelkami powietrza zamkniętymi pod wodą. Logiczne jest, że im są one większe tym szybciej wypływają na powierzchnię. Na dość podobnej zasadzie działa sortowanie bąbelkowe, ponieważ "wypycha" ono największy składnik na koniec. W naszych kodach będziemy przedstawiać wszystko na tablicy liczb całkowitych. Ale oczywiście można to zrobić na innych. A do zamiany stosowany jest wcześniej opisany algorytm swap. Algorytm polega na tym, że przegląda w tablicy 2 sąsiednie elementy. Jeśli pierwszy jest większy od drugiego to zamienia je miejscami. (Ważna jest tutaj kolejność elementów.) Następnie porównuje drugi element i trzeci. I tak, aż do końca tablicy. Wtedy ostatni jej element jest największym. (Ale reszta jest nieposortowana.) Aby ją poukładać należy ponownie wywołać algorytm dla tej samej tablicy (można dla tablicy bez ostatniego elementu).

Nasza przykładowa tablica wygląda następująco:
6 7 4 1
1. Porównujemy pierwsze 2 elementy: 6 i 7... Są one w dobrej kolejności.
6 7 4 1
2. Przechodzimy do następnej pary "7 i 4". 7>4 więc zamieniamy je miejscami.
6 4 7 1
3. Dalej porównujemy 7 i 1. 7>1 więc zamieniamy. jak widać po tym kroku największa liczba jest już na końcu tablicy.
6 4 1 7
4. Zaczynamy przeglądać tablicę od początku. 6>4
4 6 1 7
5. Kolejna para 6>1. Znów zamiana. I kolejna 6<7
4 1 6 7
6. Zaczynamy od początku sortować po raz ostatni. 4>1 zamieniamy je miejscami. Reszta jest już poukładana dobrze więc nic w kolejnych krokach się nie robi. Czyli algorytm jest zakończony.
1 4 6 7

Sortowanie to musi zrobić n-1 obiegów (Gdzie n to liczba elementów w tablicy.) i w każdym obiegu wykonać max. n-1 porównań. Dlatego ma złożoność rzędu O(n²). Można oczywiście to uprościć gdyż po pierwszym przejściu ostatni element jest ustawiony poprawnie, co za tym idzie możemy w kolejnym przejściu nie sprawdzać ostatniego elementu z poprzednim, lecz nieznacznie to skróci czas wykonywania operacji dla tablic. A na małych tablicach będzie to wręcz niezauważalne.