Sortowanie bąbelkowe

🎯 Po co Ci to?

Wchodzimy do kuchni sortowania — i zaczynamy od algorytmu, którego nikt nie używa w produkcji, a każdy informatyk świata zna go na pamięć. Paradoks? Nie: bąbelkowe jest dla sortowań tym, czym rower treningowy dla kolarstwa. Jest tak proste, że całą uwagę możesz poświęcić rzeczom, które w sortowaniu naprawdę trudne: liczeniu porównań i zamian, rozumowaniu „dlaczego to na pewno się kończy i na pewno sortuje" i pierwszym optymalizacjom. A nazwa — zobaczysz — jest najładniejsza w całej informatyce.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

• wykonać i zaprogramować sortowanie bąbelkowe;
• uzasadnić jego poprawność („po $i$-tym przebiegu $i$ największych stoi na miejscu");
• policzyć koszt $\sim n^2$ i przyspieszyć algorytm flagą wczesnego wyjścia.

📘 Wyjaśnienie

Pomysł. Idź wzdłuż listy i porównuj sąsiadów: jeśli stoją w złej kolejności (lewy większy) — zamień. Po jednym takim przebiegu największy element „przebąbelkuje" na sam koniec, jak bańka powietrza w wodzie — stąd nazwa. Powtórz przebieg dla reszty; po $n-1$ przebiegach wszystko stoi.

def babelkowe(L):
    n = len(L)
    for i in range(n - 1):                 # przebiegi
        for j in range(n - 1 - i):         # sąsiedzi: coraz krótszy odcinek!
            if L[j] > L[j + 1]:
                L[j], L[j + 1] = L[j + 1], L[j]     # zamiana sąsiadów

Dwa smaczki. Zamiana L[j], L[j+1] = L[j+1], L[j] to podmiana równoczesna (znasz ją z Fibonacciego 4.3 — bez niej potrzebowałbyś zmiennej pomocniczej). A zasięg wewnętrznej pętli maleje z każdym przebiegiem (n - 1 - i): skoro po pierwszym przebiegu największy element stoi na końcu, nie ma po co go więcej odwiedzać. Ta obserwacja to zarazem dowód poprawności: po $i$ przebiegach ostatnie $i$ elementów to $i$ największych, we właściwej kolejności (niezmiennik! — jak przy binarnym); po $n-1$ przebiegach niezmiennik obejmuje całą listę.

Koszt. Porównań: $(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}$ — suma Gaussa z 1.5, tym razem w roli rachunku kosztów! Dla $n = 1000$: pół miliona porównań; dla miliona elementów: pół biliona — kwadratowy wzrost, o którym ostrzegał algorytm C z jednostki 1.5. Zamian bywa od zera (lista już posortowana) do tyluż co porównań (lista odwrócona).

💭 Pomyśl: Lista [1, 2, 3, 4, 5] jest już posortowana. Ile porównań i ile zamian wykona na niej babelkowe? Co Cię w tej odpowiedzi drażni?

def babelkowe_flaga(L):
    n = len(L)
    for i in range(n - 1):
        bylo = False
        for j in range(n - 1 - i):
            if L[j] > L[j + 1]:
                L[j], L[j + 1] = L[j + 1], L[j]
                bylo = True
        if not bylo:
            return                     # przebieg bez zamian = koniec pracy

🧮 Prześledź

Posortuj bąbelkowo [5, 1, 4, 2] — wypisz listę po każdej zamianie (nie tylko po przebiegach).

⚠️ Uwaga, pułapka

babelkowe(L) sortuje listę w miejscu — zmienia dane wywołującego (lista to wspólny obiekt, 3.4!). To bywa pożądane (oszczędność pamięci) i bywa katastrofą (kolejność „oryginalna" przepada bezpowrotnie). Obie umowy są legalne — sortowanie w miejscu albo zwracanie posortowanej kopii — ale specyfikacja musi mówić, którą zawarto, a wywołujący musi wiedzieć. Wbudowane narzędzia Pythona oferują obie: L.sort() w miejscu, sorted(L) — kopia.

🛠️ Teraz Ty

Bez komputera: posortuj bąbelkowo (z notowaniem zamian) listę ocen [3, 6, 2, 6, 1]. Z komputerem: zaimplementuj wersję z flagą i dołóż liczniki porównań i zamian; uruchom na trzech listach po 20 elementów — posortowanej, odwróconej i losowej — i zanotuj wyniki. Te trzy liczby wrócą w 6.5 jako materiał dowodowy.

📐 Definicje tej lekcji

• Sortowanie bąbelkowe — przebiegi zamian sąsiadów; po $i$-tym przebiegu $i$ największych elementów stoi na końcu.
• Flaga wczesnego wyjścia — przebieg bez zamian kończy sortowanie; najlepszy przypadek spada do $n-1$ porównań.
• Sortowanie w miejscu — algorytm przestawia elementy w oryginalnej liście, zamiast budować nową.

📌 Najważniejsze w pigułce

• Porównuj sąsiadów, zamieniaj złe pary; największy bąbelkuje na koniec — to zarazem szkic dowodu poprawności.
• Koszt $\frac{n(n-1)}{2}$ porównań — Gauss w rachunku kosztów; kwadrat rośnie bezlitośnie.
• Flaga „bez zamian = koniec" ratuje najlepszy przypadek; o umowie „w miejscu czy kopia" mówi specyfikacja.

🎒 Zadania

1. Ile dokładnie porównań i zamian wykona bąbelkowe (bez flagi) na liście [4, 3, 2, 1]? Zapisz stan po każdym przebiegu.

2. W bąbelkowym zamieniamy tylko sąsiadów. Uzasadnij, że liczba zamian, którą musi wykonać (na dowolnej liście), jest równa liczbie par elementów stojących w złej kolejności (tzw. inwersji) — i policz inwersje w [3, 1, 4, 2].

3. Zaproponuj dane, na których wersja z flagą jest dramatycznie szybsza od wersji bez flagi, oraz takie, na których flaga nic nie daje. Sformułuj regułę: kiedy flaga się opłaca?

🔍 Sprawdź, czy umiesz

• Wykonać bąbelkowe na kartce, licząc porównania i zamiany.
• Wypowiedzieć niezmiennik przebiegów i wyprowadzić z niego poprawność.
• Dodać flagę i wskazać dane, na których zmienia ona świat.