Sortowanie Bąbelkowe (Bubble Sort) na Maturze z Informatyki
Sortowanie bąbelkowe to jeden z najprostszych algorytmów sortowania, jaki poznasz. Jego nazwa wzięła się z analogii do bąbelków powietrza w wodzie – elementy 'lżejsze' (mniejsze liczby) stopniowo 'wypływają' na początek tablicy, a 'cięższe' (większe liczby) 'toną' na jej koniec. Algorytm ten działa poprzez wielokrotne przechodzenie przez tablicę, porównywanie sąsiednich elementów i zamienianie ich miejscami, jeśli są w złej kolejności. Jest to świetny algorytm do nauki podstaw sortowania, ponieważ jego logika jest bardzo intuicyjna. Chociaż jest prosty do zrozumienia i zaimplementowania, rzadko jest najlepszym wyborem w praktyce z powodu swojej niskiej wydajności dla dużych zbiorów danych.
Dlaczego to ważne? Na maturze sortowanie bąbelkowe jest ważne z dwóch powodów. Po pierwsze, jest tak proste, że możesz je napisać z pamięci w 3 minuty, jeśli będziesz potrzebować jakiegokolwiek działającego sortowania dla małego zbioru danych. Po drugie, CKE lubi pytać o algorytmy o złożoności kwadratowej (O(n²)) w zadaniach teoretycznych, np. o śledzenie liczby zamian lub porównań. Musisz je rozumieć, nawet jeśli w praktyce będziesz używać wbudowanej funkcji .sort().
Teoria
Główna idea polega na wielokrotnym przechodzeniu przez tablicę i porównywaniu par sąsiednich elementów (tab[j] i tab[j+1]). Jeśli elementy są w złej kolejności (np. tab[j] > tab[j+1] przy sortowaniu rosnącym), zamieniamy je miejscami. Powtarzamy ten proces (przejście) tyle razy, aż tablica będzie posortowana.
Jak to działa?
- Krok 1: Rozpocznij pętlę zewnętrzną 'i', która wykona się n-1 razy (gdzie 'n' to liczba elementów). Ta pętla odpowiada za liczbę 'przejść' przez tablicę.
- Krok 2: Wewnątrz pętli 'i', uruchom pętlę wewnętrzną 'j', która będzie przechodzić od początku tablicy do
n-i-1. - Krok 3: (Optymalizacja
n-i-1): Po każdym przejściu 'i', największy element z niesortowanej części 'ląduje' na końcu. Nie musimy więc już sprawdzać posortowanego 'ogona' tablicy. - Krok 4: W pętli 'j', porównaj
tab[j]ztab[j+1]. - Krok 5: Jeśli
tab[j] > tab[j+1], zamień je miejscami (operacja 'swap'). - Krok 6: Po zakończeniu obu pętli, tablica jest posortowana.
Złożoność: Złożoność czasowa: O(n²) (kwadratowa). W najgorszym (i średnim) przypadku musimy wykonać mniej więcej n*n porównań. Dzieje się tak z powodu dwóch zagnieżdżonych pętli, z których każda jest zależna od 'n'. To sprawia, że algorytm jest bardzo wolny dla dużych 'n' (np. n > 10 000). Złożoność pamięciowa: O(1) (stała), ponieważ sortujemy tablicę 'w miejscu' (in-place) i potrzebujemy co najwyżej jednej dodatkowej zmiennej do zamiany.
Implementacja
To jest klasyczna, zoptymalizowana implementacja. `n = len(tab)`. Pętla zewnętrzna `i` idzie od 0 do `n-2`. Pętla wewnętrzna `j` idzie od 0 do `n-i-2`. W Pythonie zamiana `tab[j], tab[j+1] = tab[j+1], tab[j]` jest bardzo wygodna.
To jest ulepszona wersja. Dodajemy flagę `swapped`. Jeśli wewnętrzna pętla przejdzie całą tablicę i nie dokona *ani jednej* zamiany, oznacza to, że tablica jest już posortowana. Wtedy `break` przerywa pętlę zewnętrzną. To znacznie przyspiesza algorytm dla danych częściowo posortowanych.
Logika jest identyczna jak w Pythonie. Używamy `vector` jako naszej tablicy. Do zamiany elementów najwygodniej użyć funkcji `swap(a, b)` z biblioteki `<algorithm>`. Zamiast `vector` można też użyć statycznej tablicy `int dane[]`, ale `vector` jest bardziej elastyczny.
Przykładowe Zadania Maturalne
W pliku 'dane.txt' znajduje się 100 liczb całkowitych, każda w osobnym wierszu. Wczytaj wszystkie liczby do tablicy. Następnie posortuj tę tablicę rosnąco, implementując algorytm sortowania bąbelkowego. Na koniec wypisz 10 najmniejszych liczb z posortowanej tablicy.
Wskazówka: Najpierw wczytaj wszystkie 100 liczb do listy (tablicy). Następnie przekaż tę listę do swojej funkcji bubble_sort(). Po posortowaniu, 10 najmniejszych liczb to będzie po prostu 10 pierwszych elementów tablicy (o indeksach od 0 do 9).
Pokaż szkic rozwiązania
1. Stwórz pustą listę `liczby = []`. 2. Otwórz plik 'dane.txt' do odczytu. 3. W pętli `for linia in plik:`: a. `liczby.append(int(linia.strip()))`. 4. Zaimplementuj funkcję `bubble_sort(tab)` (jak w przykładzie kodu). 5. Wywołaj sortowanie na wczytanych danych: `bubble_sort(liczby)`. 6. Po posortowaniu, wypisz 10 pierwszych elementów: a. `for i in range(10):` b. ` print(liczby[i])`.
Dana jest dodatnia liczba całkowita n oraz słowo s[1..n]. Naszym celem jest obliczenie wartości elementów tablicy T[1..n] zawierającej numery sufiksów słowa s[1..n] uporządkowanych w porządku alfabetycznym. Zapisz w wybranej przez siebie notacji algorytm, który obliczy wartości elementów tablicy T. Możesz wykorzystać funkcję czy_mniejszy(n, s, k1, k2) podaną w arkuszu.
Wskazówka: To zadanie wprost prosi o algorytm sortujący. Twoim zadaniem jest posortowanie tablicy indeksów T = [1, 2, 3, ..., n]. Użyj sortowania bąbelkowego, ale zamiast porównywać T[j] > T[j+1], musisz użyć podanej funkcji czy_mniejszy(n, s, T[j+1], T[j]), aby sprawdzić, czy sufiks o indeksie T[j+1] jest alfabetycznie mniejszy niż sufiks o indeksie T[j].
Pokaż szkic rozwiązania
1. Wczytaj `n` oraz słowo `s`. 2. Stwórz tablicę `T` wypełnioną liczbami od 1 do n (np. w Pythonie `T = list(range(1, n + 1))`). 3. Zaimplementuj funkcję `czy_mniejszy(n, s, k1, k2)` (zgodnie z treścią zadania). 4. Zastosuj sortowanie bąbelkowe na tablicy `T`: a. `for i in range(n - 1):` b. ` for j in range(n - i - 1):` c. ` # Sprawdź, czy T[j+1] jest mniejszy niż T[j]` d. ` if czy_mniejszy(n, s, T[j + 1], T[j]):` e. ` # Zamień elementy w tablicy T` f. ` T[j], T[j + 1] = T[j + 1], T[j]` 5. Po zakończeniu pętli tablica `T` zawiera posortowane indeksy sufiksów.
Częste Błędy
❌ Używanie Bubble Sort dla dużych danych
Sortowanie bąbelkowe ma złożoność O(n²). Dla n=3000 (jak w niektórych zadaniach) daje to 9,000,000 operacji, co jest na granicy limitu czasu. Dla n=100,000 (10 miliardów operacji) na pewno przekroczy limit czasu.
Poprawka: Jeśli masz posortować duży zbiór (n > ok. 5000) i nie ma wymogu implementacji algorytmu, zawsze używaj wbudowanej funkcji list.sort() (w Pythonie) lub std::sort() (w C++). Działają one w czasie O(n log n).
❌ Błąd 'Off-by-One' w pętlach
Bardzo częsty błąd. Pętla zewnętrzna powinna iść n-1 razy (range(n-1)). Pętla wewnętrzna musi się skracać (range(n-i-1)), a wewnątrz niej odwołujemy się do j oraz j+1. Łatwo tu wyjść poza zakres tablicy.
Poprawka: Zapamiętaj wzorzec: for i in range(n-1): i for j in range(n-i-1):. To najbezpieczniejsza kombinacja.
❌ Błędna implementacja zamiany (swap)
W C++ pomyłka typu: temp = a; a = b; b = a; (zamiast b = temp). W Pythonie błąd jest rzadszy, ale możliwy.
Poprawka: W C++ trzymaj się schematu: temp = a; a = b; b = temp; lub użyj swap(a, b). W Pythonie używaj a, b = b, a.
❌ Sortowanie rosnąco zamiast malejąco (i na odwrót)
Zadanie prosi o sortowanie malejąco, a ty piszesz if tab[j] > tab[j+1]. To sortuje rosnąco.
Poprawka: Aby sortować rosnąco, zamieniaj gdy tab[j] > tab[j+1]. Aby sortować malejąco, zamieniaj gdy tab[j] < tab[j+1].
Kluczowe Wnioski
- Sortowanie bąbelkowe to prosty, ale wolny algorytm sortowania o złożoności O(n²).
- Jego główna idea to porównywanie i zamienianie sąsiednich elementów (
tab[j]itab[j+1]). - Posiada dwie zagnieżdżone pętle FOR.
- Jest to algorytm 'stabilny' i 'w miejscu' (O(1) pamięci).
- Na maturze używaj wbudowanego
.sort()(O(n log n)), chyba że zadanie każe zaimplementować własny algorytm lub dane są bardzo małe. - Wersja zoptymalizowana z flagą
swappedprzerywa sortowanie, gdy tablica jest już uporządkowana (najlepszy przypadek O(n)).
Najczęściej Zadawane Pytania
❓ Czy mogę użyć wbudowanej funkcji .sort() na maturze?
Tak! Jest to nawet zalecane. Używaj `nazwa_listy.sort()` (w Pythonie) lub `sort(nazwa_wektora.begin(), nazwa_wektora.end())` (w C++) zawsze, gdy zadanie polega na sortowaniu, ale nie wymaga implementacji *konkretnego* algorytmu (jak bubble sort).
❓ Dlaczego złożoność bubble sort to O(n^2)?
Wyobraź sobie tablicę 100-elementową. Pętla zewnętrzna wykona się ok. 100 razy. Dla każdego z tych 100 przejść, pętla wewnętrzna wykona się (średnio) ok. 50 razy. To daje 100 * 50 = 5000 operacji. Dla n, jest to (n-1) * (n/2) operacji, co po uproszczeniu daje O(n^2).
❓ Dlaczego pętla wewnętrzna jest do `n-i-1`?
To optymalizacja. Po pierwszym przejściu (i=0), największy element jest na 100% na ostatnim miejscu (`n-1`). Po drugim przejściu (i=1), dwa największe są na miejscach `n-2` i `n-1`. Nie ma sensu ich ponownie sprawdzać. Ta optymalizacja skraca pętlę wewnętrzną o 1 w każdej iteracji zewnętrznej.
❓ Czy sortowanie bąbelkowe jest 'stabilne'?
Tak. 'Stabilne' sortowanie oznacza, że elementy o tej samej wartości zachowują swoją pierwotną kolejność. Ponieważ sortowanie bąbelkowe zamienia elementy tylko wtedy, gdy `tab[j] > tab[j+1]`, dwa równe elementy (`tab[j] == tab[j+1]`) nigdy nie zostaną zamienione.
❓
Chcesz opanować wszystkie tematy maturalne?
Dołącz do kursu i zyskaj dostęp do interaktywnych lekcji, edytora kodu i setek zadań.