Jak nazywa się metoda sortowania, polegająca na wielokrotnym przeglądaniu kolejnych elementów tablicy i zamianie miejscami elementów sąsiadujących tak, aby zachowały regułę porządkującą?
A. Sortowanie przez wybór.
B. Sortowanie bąbelkowe.
C. Sortowanie kubełkowe.
D. Sortowanie szybkie.
Pytanie z egzaminu CKE, czerwiec 2023 (arkusz EE.09-SG-23.06).
Opis w pytaniu jednoznacznie wskazuje na sortowanie bąbelkowe, bo jego główną cechą jest porównywanie elementów sąsiadujących i zamienianie ich miejscami, jeśli są w złej kolejności. Algorytm przechodzi po tablicy wiele razy, a po każdym pełnym przejściu jeden z elementów trafia na swoje docelowe miejsce, tak jakby większe wartości „wypływały” na koniec tablicy. Stąd właśnie nazwa bąbelkowe. Przykładowo dla tablicy 5, 2, 8, 1 algorytm porówna 5 z 2, zamieni je, potem porówna 5 z 8, zostawi, następnie 8 z 1 i znów zamieni. W praktyce to dobry algorytm do nauki zasad sortowania, pętli zagnieżdżonych i pracy na indeksach tablicy, np. w JavaScript, PHP czy C++. Moim zdaniem warto go znać, mimo że w prawdziwych systemach rzadko używa się go do dużych danych, bo ma złożoność czasową $O(n^2)$. Dobrą praktyką jest rozumieć jego działanie, ale przy większych kolekcjach stosować wydajniejsze mechanizmy sortujące dostępne w bibliotekach języka albo algorytmy typu quicksort, mergesort czy sortowanie hybrydowe.
W tym pytaniu łatwo pomylić kilka popularnych metod sortowania, bo każda z nich prowadzi do tego samego celu, czyli uporządkowania danych. Różnią się jednak sposobem działania, a właśnie sposób działania jest tutaj kluczowy. Sortowanie przez wybór polega na wyszukiwaniu najmniejszego albo największego elementu w nieposortowanej części tablicy i przenoszeniu go na odpowiednią pozycję. Nie wykonuje ono typowego, ciągłego porównywania par sąsiadów i zamieniania ich miejscami po kolei. To częsty błąd myślowy: ktoś widzi zamiany elementów i od razu zakłada, że każdy algorytm sortowania robi to tak samo.Sortowanie szybkie działa zupełnie inaczej. Wybiera element zwany pivotem i dzieli dane na mniejsze oraz większe względem tego elementu, a potem rekurencyjnie porządkuje powstałe części. W praktyce quicksort jest dużo bardziej wydajny dla dużych zbiorów niż bąbelkowe, choć wymaga lepszego rozumienia rekurencji i podziału problemu. Sortowanie kubełkowe także nie pasuje do opisu, bo rozdziela dane do kubełków, czyli przedziałów wartości, a dopiero potem porządkuje zawartość tych kubełków. Stosuje się je raczej wtedy, gdy znamy rozkład danych i zakres wartości. Opis wielokrotnego przechodzenia przez tablicę oraz porównywania sąsiednich elementów to klasyczny schemat sortowania bąbelkowego. Z mojego doświadczenia najlepiej zapamiętać to obrazowo: elementy są porównywane parami, a większe stopniowo przesuwają się w stronę końca tablicy, jak bąbelki do góry.