Algorytm sortowania bąbelkowego

Sortowanie bąbelkowe (ang. bubble sort) to jeden z najprostszych do zrozumienia algorytmów sortowania i klasyczny punkt wyjścia do nauki analizy złożoności obliczeniowej na maturze rozszerzonej z informatyki. Jego zasada działania opiera się na wielokrotnym porównywaniu sąsiednich elementów tablicy i zamianie ich miejscami, jeśli są ustawione w złej kolejności — w efekcie największe elementy stopniowo "wypływają" (jak bąbelki) na koniec tablicy.

Lekcja szczegółowo omawia mechanikę pojedynczej iteracji: dla tablicy o $n$ elementach pierwsze przejście wymaga $n-1$ porównań sąsiednich par. Po zakończeniu pierwszej pełnej iteracji największy element zawsze znajduje się na ostatniej pozycji, co pozwala w każdej kolejnej iteracji skracać zakres przeszukiwania o jeden element. Uczeń uczy się liczyć całkowitą liczbę porównań w najgorszym przypadku, która wynosi $\frac{n(n-1)}{2}$ — sumę ciągu arytmetycznego.

Materiał obejmuje analizę złożoności obliczeniowej w trzech scenariuszach: najgorszym (tablica odwrócona, $O(n^2)$), najlepszym (tablica już posortowana — z zastosowaniem optymalizacji flagowej algorytm wykonuje jedynie $O(n)$ operacji) oraz omawia stałą złożoność pamięciową $O(1)$, ponieważ sortowanie odbywa się w miejscu (in-place), bez potrzeby dodatkowej struktury danych.

Kluczowym elementem jest optymalizacja z flagą "czy_byla_zamiana": jeśli w danym pełnym przejściu przez tablicę nie wykonano żadnej zamiany, oznacza to, że tablica jest już posortowana i algorytm może zakończyć działanie wcześniej, zamiast wykonywać wszystkie zaplanowane iteracje. To ważna optymalizacja praktyczna, którą uczniowie często pomijają w prostych implementacjach.

Zadania obejmują też ręczne śledzenie kroków algorytmu na konkretnym przykładzie — na przykład prześledzenie, ile zamian wymaga posortowanie tablicy $[3, 2, 1]$ — oraz analizę cech algorytmu: stabilności (sortowanie bąbelkowe zachowuje względną kolejność elementów o tych samych wartościach) i charakteru porównawczego. Uczeń poznaje też, dlaczego mimo prostoty implementacji sortowanie bąbelkowe jest rzadko stosowane w praktyce dla dużych zbiorów danych — z powodu niekorzystnej złożoności kwadratowej w porównaniu z algorytmami takimi jak sortowanie szybkie (quicksort).

Ten zestaw pytań i fiszek utrwala zarówno intuicję algorytmiczną, jak i formalne rachunki złożoności obliczeniowej niezbędne na egzaminie maturalnym.

• Uczeń opisuje zasadę działania algorytmu sortowania bąbelkowego krok po kroku
• Uczeń oblicza liczbę porównań w pierwszej iteracji oraz w całym algorytmie dla danej wielkości tablicy n
• Uczeń rozróżnia złożoność czasową w najlepszym (O(n)) i najgorszym (O(n²)) przypadku
• Uczeń rozumie zasadę optymalizacji z flagą wykrywającą brak zamian w danej iteracji
• Uczeń wie, że sortowanie bąbelkowe jest stabilne i ma stałą złożoność pamięciową O(1)
• Uczeń potrafi ręcznie prześledzić kolejne kroki sortowania konkretnego ciągu liczb
• Uczeń wyjaśnia, dlaczego sortowanie bąbelkowe jest nieefektywne dla dużych zbiorów danych

Materiał tematyczny (bez dokumentu źródłowego): algorytm sortowania bąbelkowego (bubble sort) — zasada działania, kolejne kroki sortowania przykładowego ciągu liczb, liczba porównań i zamian, złożoność obliczeniowa, zgodnie z zakresem matury rozszerzonej z informatyki.