Lekcja 3. Algorytmy sortowania — bąbelkowe i przez scalanie (dziel i zwyciężaj)
ŚredniPo co się tego uczymy?
Sortowanie to jedna z najczęściej wykonywanych operacji w informatyce — a strategia "dziel i zwyciężaj" (poznana tu na przykładzie sortowania przez scalanie) to jeden z najważniejszych, uniwersalnych sposobów myślenia o dużych problemach, wymagany na maturze rozszerzonej.
Teoria
Rekursja (ang. recursion) to sytuacja, w której funkcja wywołuje SAMĄ SIEBIE, aż do osiągnięcia warunku stopu. Klasyczny przykład — silnia: silnia(n) = n * silnia(n-1), z warunkiem stopu silnia(0) = 1.
Strategia "dziel i zwyciężaj" (divide and conquer) to sposób rozwiązywania problemów w trzech krokach: Podziel (Divide) — duży problem dzielimy na mniejsze, prostsze podproblemy; Rozwiąż (Conquer) — rozwiązujemy każdy podproblem (najczęściej rekurencyjnie); Połącz (Combine) — składamy rozwiązania podproblemów w całość. Wyszukiwanie binarne (poprzednia lekcja) to najprostszy przykład tej strategii — za każdym razem bierzemy tylko połowę listy i rozwiązujemy problem tak samo (rekurencyjnie) na mniejszym fragmencie.
Sortowanie przez scalanie (MergeSort) to algorytm sortowania oparty WŁAŚNIE na strategii dziel i zwyciężaj: (1) dzielimy tablicę na dwie połowy, (2) sortujemy REKURENCYJNIE każdą połowę, (3) SCALAMY (łączymy) obie posortowane listy w jedną posortowaną całość. Cechy: zawsze działa w czasie O(n log n) niezależnie od danych wejściowych, wymaga dodatkowej pamięci na proces scalania (O(n)), jest STABILNY (zachowuje kolejność elementów równych).
Proces scalania dwóch posortowanych list — porównujemy PIERWSZE elementy obu list, bierzemy MNIEJSZY z nich do wyniku, i powtarzamy, aż jedna z list się skończy — wtedy dokładamy resztę drugiej.
Sortowanie bąbelkowe (BubbleSort) to jeden z najprostszych algorytmów sortowania — NIE stosuje strategii dziel i zwyciężaj, tylko wielokrotnie przechodzi przez tablicę, porównując SĄSIEDNIE elementy i zamieniając je miejscami, jeśli są w złej kolejności. Największe elementy stopniowo "wypływają" na koniec tablicy — jak bąbelki powietrza w wodzie (stąd nazwa). Prostszy w implementacji niż MergeSort, ale znacznie WOLNIEJSZY dla dużych zbiorów danych (złożoność O(n²) kontra O(n log n)).
Schemat
MERGESORT (dziel i zwyciężaj):
[42, 17, 23, 17, 58, 34]
↓ DZIEL na połowy
[42, 17, 23] [17, 58, 34]
↓ dziel dalej ↓ dziel dalej
[42][17,23] [17][58,34]
↓ scal ↓ scal
[42][17,23]→[17,23] [17][34,58]→[17,34,58]
↓ scal ↓
[17,23,42] [17,34,58]
↓ SCAL OBIE POŁÓWKI
[17, 17, 23, 34, 42, 58]
BUBBLESORT (porównania sąsiadów, [5,3,8,4,2]):
przejście 1: 5,3→zamiana | 3,5,8→bez | 8,4→zamiana | 8,2→zamiana → [3,5,4,2,8]
przejście 2-4: kolejne przejścia "wypychają" coraz mniejsze liczby w lewo
wynik: [2, 3, 4, 5, 8]
Przykład z życia
Sortowanie listy uczniów wg średniej ocen w dzienniku elektronicznym, sortowanie wyników wyszukiwania w sklepie internetowym wg ceny, sortowanie zdjęć wg daty w telefonie — wszystkie te operacje "pod maską" korzystają z algorytmów bardzo podobnych do MergeSort, bo jest szybki i przewidywalny nawet dla milionów elementów.
mergesort.py
# Rekursja - przypomnienie (silnia)
def silnia(n):
if n == 0:
return 1 # warunek stopu
else:
return n * silnia(n-1)
# MergeSort - sortowanie przez scalanie (dziel i zwyciężaj)
def scalaj(lewa, prawa):
wynik = []
i = j = 0
# dopóki w obu listach są elementy
while i < len(lewa) and j < len(prawa):
if lewa[i] <= prawa[j]:
wynik.append(lewa[i])
i += 1
else:
wynik.append(prawa[j])
j += 1
# dokładamy resztę (jedna z list mogła się skończyć wcześniej)
wynik.extend(lewa[i:])
wynik.extend(prawa[j:])
return wynik
def mergesort(tab):
if len(tab) <= 1: # warunek stopu
return tab
srodek = len(tab) // 2
lewa = mergesort(tab[:srodek]) # rekurencyjnie sortujemy lewą
prawa = mergesort(tab[srodek:]) # rekurencyjnie sortujemy prawą
return scalaj(lewa, prawa) # scalanie
# przykład
punkty = [42, 17, 23, 17, 58, 34]
print("Posortowane:", mergesort(punkty))
# Wynik: Posortowane: [17, 17, 23, 34, 42, 58]bubble_sort.py
# BubbleSort - sortowanie bąbelkowe (proste, ale wolniejsze - O(n^2))
def bubble_sort(tab):
n = len(tab)
for i in range(n-1): # powtarzamy n-1 razy
for j in range(n-1-i): # za każdym razem o 1 porównanie mniej
if tab[j] > tab[j+1]:
# zamiana miejscami
tab[j], tab[j+1] = tab[j+1], tab[j]
return tab
# przykład
dane = [5, 3, 8, 4, 2]
print("Posortowane:", bubble_sort(dane))
# Wynik: Posortowane: [2, 3, 4, 5, 8]Komentarz i wyjaśnienie kodu
W mergesort() warunek stopu if len(tab) <= 1 mówi: LISTA JEDNOELEMENTOWA (albo pusta) jest Z DEFINICJI posortowana — nie trzeba jej już dzielić. Cała "magia" dzieje się w scalaj(), która ZAWSZE łączy dwie JUŻ POSORTOWANE listy, porównując ich czoła.
W bubble_sort() zewnętrzna pętla for i in range(n-1) kontroluje liczbę PRZEJŚĆ przez tablicę, a wewnętrzna range(n-1-i) z każdym przejściem sprawdza O JEDEN ELEMENT MNIEJ — bo po każdym przejściu kolejny "najcięższy" element trafia na swoje ostateczne miejsce na końcu i nie trzeba go już porównywać.
Ćwiczenie samodzielne
Uruchom mergesort() i bubble_sort() dla tej samej listy 6-8 losowych liczb i porównaj wynik. Prześledź ręcznie na kartce, jak dzieli się lista w MergeSort, aż dojdzie do pojedynczych elementów.
Zadania do pracy własnej
Posortuj listę wyników testu uczniów
[42, 17, 23, 17, 58, 34]algorytmem bąbelkowym — wypisz stan tablicy PO KAŻDYM przejściu zewnętrznej pętli.Zaimplementuj funkcję
scalaj()samodzielnie (bez podglądania przykładu) i przetestuj ją na dwóch już posortowanych listach:[1, 4, 7]i[2, 3, 9].Zmodyfikuj
mergesort()tak, żeby przy każdym wywołaniu wypisywała, na jakie dwie części dzieli aktualną listę — uruchom dla listy 8-elementowej i prześledź CAŁE drzewo podziałów i scaleń, porównując je z wynikiem ręcznych obliczeń.
Typowe błędy
Zapominanie o warunku stopu w rekurencji (if len(tab) <= 1: return tab) — bez niego mergesort() próbowałby dzielić listę w nieskończoność.
Błędna kolejność porównań w scalaj() — jeśli pomylisz <= z >=, scalanie odwróci kolejność zamiast ją zachować.
Przekonanie, że BubbleSort "wystarczy" dla dużych zbiorów danych — dla 10 elementów różnica między BubbleSort (O(n²)) a MergeSort (O(n log n)) jest niezauważalna, ale dla 1 000 000 elementów BubbleSort może być TYSIĄCE razy wolniejszy.
Nawiązanie do egzaminu zawodowego
Strategia "dziel i zwyciężaj" (MergeSort) i jej złożoność O(n log n) w porównaniu do O(n²) sortowania bąbelkowego to klasyczny temat analizy algorytmów na maturze rozszerzonej — bezpośrednio przygotowuje do lekcji o analizie złożoności obliczeniowej (ostatnia lekcja tego działu) oraz o programowaniu dynamicznym, który rozwija ideę "dziel na mniejsze podproblemy" o dodatkowe zapamiętywanie wyników.