Sortowanie bąbelkowe
Raz po raz przechodzi przez listę i zamienia miejscami sąsiadów w złej kolejności. Po każdym przejściu największa z pozostałych wartości jest na końcu.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- tak
- tak
Najlepszy przypadek: jak czas rośnie z rozmiarem listy n, gdy dane są dla tego algorytmu najłatwiejsze.
Średni: jak czas zwykle rośnie z n. Przy n² dwa razy więcej wartości sortuje się około czterech razy dłużej; n log n rośnie dużo wolniej.
Najgorszy przypadek: jak rośnie czas przy najtrudniejszych danych. Ważny, gdy sortowanie nigdy nie może zwolnić.
Pamięć: ile dodatkowej pamięci potrzeba poza listą. 1 to kilka zmiennych, n to kopia listy.
Stabilny: dwie równe wartości zachowują pierwotną kolejność. Ważne przy sortowaniu rekordów według jednego pola.
Bez dodatkowej pamięci: sortuje w samej liście, bez drugiej listy.
- porównywanie
- przenoszenie
- na właściwym miejscu
Spróbuj: Wybierz listę prawie posortowaną. Po przejściu bez żadnej zamiany algorytm kończy wcześniej.
Jak to działa
Porównuje dwie sąsiednie wartości i zamienia je miejscami, gdy lewa jest większa. Dzięki temu w każdym przejściu największa wartość wędruje aż na prawy koniec, jak bąbelek wypływający w górę. Przejście bez żadnej zamiany oznacza, że lista jest już posortowana.
Kiedy warto go użyć
W prawdziwych programach prawie nigdy, bo na długich listach działa wolno. Za to świetnie nadaje się do nauki: pokazuje, na czym polega sortowanie przez porównywanie i zamiany. Szybkie jest tylko na liście już posortowanej.