Sortowanie bąbelkowe

Sortowanie bąbelkowe to najprostszy do opisania algorytm sortowania: porównaj dwóch sąsiadów, zamień ich, jeśli są w złej kolejności, i powtarzaj. Na długich listach jest wolne, ale każdy krok łatwo śledzić, dlatego to klasyczny pierwszy algorytm do obejrzenia.

Słupki różnej wysokości podczas sortowania, dwa sąsiednie podświetlone do zamiany, a najwyższe już na swoich miejscach na końcu
Słupki różnej wysokości podczas sortowania, dwa sąsiednie podświetlone do zamiany, a najwyższe już na swoich miejscach na końcu

Idea

Przejdź przez listę od lewej do prawej i patrz na każdą parę sąsiadów. Jeśli lewa wartość jest większa od prawej, zamień je. Gdy dojdziesz do końca, największa wartość zostanie przeniesiona aż na ostatnie miejsce, tak jak bąbelek wypływa na powierzchnię. Takie przejście nazywa się przebiegiem. Powtarzaj przebiegi, aż lista będzie posortowana.

Przykład

Weź 5, 1, 4, 2, 8. Pierwszy przebieg porównuje 5 i 1 i zamienia je, potem 5 i 4 (zamiana), 5 i 2 (zamiana) oraz 5 i 8 (bez zamiany): 1, 4, 2, 5, 8. Liczba 8 jest już na swoim miejscu. Drugi przebieg porównuje 1 i 4 (bez zamiany), 4 i 2 (zamiana) oraz 4 i 5 (bez zamiany): 1, 2, 4, 5, 8. Trzeci przebieg nie wykonuje żadnej zamiany, więc lista jest posortowana: 9 porównań i 4 zamiany.

Dlaczego każdy przebieg ustawia o jedną wartość więcej

Podczas przebiegu największa dotąd widziana wartość jest zawsze niesiona dalej: gdy przebieg do niej dotrze, każde porównanie przesuwa ją o jedno miejsce w prawo. Pierwszy przebieg stawia więc największą wartość na końcu, drugi drugą co do wielkości tuż przed nią i tak dalej. Po przebiegu k ostatnie k miejsc jest ostatecznych, a następny przebieg może skończyć się o jedno miejsce wcześniej. Dlatego przebiegi są coraz krótsze.

Zamian jest tyle, ile inwersji

Inwersja to para wartości w złej kolejności: większa wartość gdzieś przed mniejszą. Zamiana dwóch sąsiadów w złej kolejności usuwa dokładnie jedną inwersję i nie tworzy nowych. Dlatego sortowanie bąbelkowe wykonuje dokładnie tyle zamian, ile inwersji ma lista początkowa, niezależnie od kolejności porównań. Lista posortowana nie ma żadnych; odwrócona lista n wartości ma ich n(n − 1)/2, najwięcej, ile się da.

Wczesne zatrzymanie i koszt

Jeśli cały przebieg nie wykona żadnej zamiany, wszyscy sąsiedzi są w dobrej kolejności i lista jest posortowana. Sprawdzanie tego pozwala skończyć posortowaną listę w jednym przebiegu z n − 1 porównaniami. W najgorszym przypadku nadal potrzeba n − 1 przebiegów i n(n − 1)/2 porównań, a średnio wykonuje się n(n − 1)/4 zamian. Obie liczby rosną jak n², więc dwa razy dłuższa lista oznacza mniej więcej cztery razy dłuższe sortowanie.

Sortowanie bąbelkowe jest stabilne: równe wartości nigdy nie są zamieniane, więc zachowują swoją kolejność. Sortuje w miejscu, bez dodatkowej pamięci. Sortowanie przez wstawianie ma te same cechy i zwykle potrzebuje mniej kroków, a sortowanie przez scalanie i quicksort działają w czasie proporcjonalnym do n log n, co na długich listach jest dużo mniej.

Wypróbuj

Otwórz aplikację i naciśnij Odtwórz albo Krok, aby przechodzić po jednym porównaniu. Dwie porównywane wartości są podświetlone, zamiana ma własny kolor, a wartości już na miejscu robią się zielone. Wybierz odwróconą listę, aby zobaczyć najgorszy przypadek, prawie posortowaną, aby zobaczyć, jak wczesne zatrzymanie kończy sortowanie po kilku przebiegach, albo wpisz liczby z przykładu powyżej.

Często zadawane pytania

Jaka jest złożoność czasowa sortowania bąbelkowego?

O(n²) w przypadku pesymistycznym i średnim: do n(n − 1)/2 porównań dla n wartości. Z wczesnym zatrzymaniem już posortowana lista wymaga O(n), czyli jednego przebiegu. Potrzeba tylko O(1) dodatkowej pamięci.

Czy sortowanie bąbelkowe jest stabilne?

Tak. Zamienia dwóch sąsiadów tylko wtedy, gdy lewy jest ściśle większy, więc równe wartości nigdy się nie mijają i zachowują pierwotną kolejność.

Czym sortowanie bąbelkowe różni się od sortowania przez wstawianie?

Oba zamieniają sąsiadów i oba wykonują tyle zamian, ile jest inwersji. Sortowanie bąbelkowe robi pełne przebiegi przez nieposortowaną część; sortowanie przez wstawianie przesuwa każdą nową wartość w lewo tylko tak daleko, jak trzeba, więc zwykle wykonuje mniej porównań, zwłaszcza na prawie posortowanych listach.

Kiedy sortowanie bąbelkowe to dobry wybór?

Głównie w nauce i przy bardzo krótkich listach, gdzie prostota liczy się bardziej niż szybkość. Przy czymś większym wbudowane sortowanie twojego języka programowania jest dużo szybsze.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Wypróbuj sortowanie bąbelkowe