Czym jest BubbleSort?
BubbleSort, czyli sortowanie bąbelkowe, to prosty algorytm sortowania oparty na wielokrotnym porównywaniu sąsiednich elementów. Jeżeli elementy są w złej kolejności, algorytm zamienia je miejscami.
Nazwa pochodzi od tego, że największe elementy „wypływają” stopniowo na koniec tablicy, podobnie jak bąbelki powietrza.
Dlaczego BubbleSort jest algorytmem iteracyjnym?
BubbleSort działa głównie za pomocą pętli. Najczęściej stosuje się dwie pętle:
- zewnętrzną — odpowiada za kolejne przebiegi sortowania,
- wewnętrzną — porównuje sąsiednie elementy tablicy.
Algorytm nie musi wywoływać samego siebie, więc nie jest typowym algorytmem rekurencyjnym.
Przykład w pseudokodzie
dla i od 0 do n-1:
dla j od 0 do n-2:
jeżeli tablica[j] > tablica[j+1]:
zamień tablica[j] z tablica[j+1]
Złożoność
- przypadek średni: O(n²),
- przypadek najgorszy: O(n²),
- przypadek najlepszy przy optymalizacji: O(n).
BubbleSort jest łatwy do zrozumienia, ale mało wydajny dla dużych zbiorów danych. Na egzaminie jest jednak częstym przykładem algorytmu iteracyjnego.