Masz listę [5, 1, 4, 2, 8] i chcesz zobaczyć, jak liczby same ustawiają się rosnąco? W sortowaniu bąbelkowym porównujesz sąsiadów i zamieniasz ich miejscami, gdy stoją w złej kolejności, choć przy dłuższej liście liczba takich kroków szybko rośnie.
Sortowanie bąbelkowe najlepiej objaśnia zamiany sąsiednich elementów
- Jeden przebieg przesuwa największy z nieuporządkowanych elementów na koniec listy.
- Wczesne zatrzymanie pozwala zakończyć algorytm, gdy cały przebieg nie wymagał zamiany.
- Średni i najgorszy przypadek wymagają czasu rzędu O(n²).
- Python ma wbudowane sortowanie przeznaczone do zwykłej pracy z listami.
Po każdym przebiegu jedna liczba trafia na właściwe miejsce
Wyobraź sobie rząd kart z liczbami. Przesuwasz się od lewej do prawej, porównując dwie sąsiednie karty; jeśli lewa ma większą wartość, zamieniasz je. Po pierwszym przejściu największa liczba ląduje na końcu, więc przy następnym przebiegu ten fragment można już pominąć.
Dla listy [5, 1, 4, 2, 8] pierwszy przebieg daje [1, 4, 2, 5, 8], a drugi [1, 2, 4, 5, 8]. Kolejny przebieg nie wykrywa żadnej pary do zamiany, więc zoptymalizowana wersja może przerwać pracę. Ten warunek końca jest łatwy do przeoczenia.
Flaga zamiany oszczędza przebiegi, ale nie ratuje trudnych danych
Bez flagi algorytm może wykonywać kolejne przebiegi nawet wtedy, gdy lista jest już uporządkowana. Zmienna zamieniono zapamiętuje, czy w danym przejściu nastąpiła choć jedna zamiana. Gdy pozostaje fałszywa, wynik jest gotowy.
def bubble_sort(lista):
wynik = lista.copy()
n = len(wynik)
for koniec in range(n - 1, 0, -1):
zamieniono = False
for i in range(koniec):
if wynik[i] > wynik[i + 1]:
wynik[i], wynik[i + 1] = wynik[i + 1], wynik[i]
zamieniono = True
if not zamieniono:
break
return wynikKopia sprawia, że funkcja zwraca posortowaną listę, a oryginał pozostaje bez zmian. Porównanie używa >, a nie >=: elementy o równych kluczach nie przeskakują nawzajem, co zachowuje ich pierwotną kolejność.
Lista pięciu liczb pokazuje, skąd bierze się koszt O(n²)
W przykładzie z początku algorytm wykonuje 9 porównań i 4 zamiany, zanim przebieg bez zamiany potwierdzi koniec sortowania. To mała lista, więc liczby operacji wyglądają niewinnie. Przy odwróconej kolejności niemal każda para sąsiadów wymaga poprawienia, a pętla przechodzi przez listę wielokrotnie.
Dla listy już uporządkowanej wersja z flagą kończy pracę po jednym przejściu, czyli wykonuje n−1 porównań. Nie zmienia to jednak obrazu dla danych losowych lub odwróconych: średni i najgorszy przypadek pozostają kwadratowe, O(n²). Właśnie dlatego sam korzystny przypadek nie wystarcza, by uznać tę metodę za szybką.
Do nauki wybierz bąbelki, do sortowania w Pythonie użyj wbudowanej metody
Sortowanie bąbelkowe jest czytelne, bo każda zmiana wynika z lokalnego porównania. Uważam, że jego najlepszym zastosowaniem jest ćwiczenie pętli, indeksów i analizy kosztu, a nie porządkowanie większych zbiorów w gotowym programie.
W codziennym kodzie Pythona wybierz sorted(dane), jeśli potrzebujesz nowej listy, albo dane.sort(), jeśli możesz zmienić istniejącą. Dokumentacja Pythona opisuje stabilność sortowania wbudowanego i podkreśla, że używany algorytm potrafi korzystać z już uporządkowanych fragmentów danych. To praktyczniejszy wybór niż ręczna implementacja, gdy celem jest po prostu wynik.
| Sytuacja | Co z niej wynika | Co zrobić |
|---|---|---|
| Chcesz prześledzić zamiany krok po kroku | Każdy ruch jest łatwy do powiązania z porównaniem sąsiadów | Użyj sortowania bąbelkowego jako ćwiczenia |
| Porządkujesz listę w zwykłym programie | Ręczna wersja wykonuje wiele porównań dla większych danych | Wybierz sorted() albo .sort() |
| Własna wersja nie kończy pracy na uporządkowanej liście | Brakuje warunku zatrzymującego po przebiegu bez zamiany | Dodaj flagę i przerwij pętlę, gdy nie wykonano zamiany |
Najlepszy test to śledzenie jednej pary aż do końca
Podczas nauki nie patrz wyłącznie na końcową listę. Zapisuj stan po każdym przebiegu i sprawdzaj, czy największy element z nieustawionej części rzeczywiście przesunął się na koniec; wtedy łatwiej wychwycić błędny zakres pętli.
Gdy celem jest działający program, postaw na funkcje wbudowane. Gdy celem jest zrozumienie, dlaczego algorytm sortuje i skąd bierze się jego koszt, kilka ręcznie prześledzonych zamian powie więcej niż samo sprawdzenie gotowego wyniku.
