Sortowanie bąbelkowe

Czym jest sortowanie bąbelkowe?

Sortowanie bąbelkowe to prosty algorytm sortowania, który wielokrotnie przechodzi przez tablicę i porównuje sąsiednie elementy. Jeśli są w złej kolejności, zamienia je miejscami. Po każdym pełnym przejściu największy element „wypływa” na koniec tablicy, podobnie jak bąbelek.

Jakie dane są potrzebne?

Do typowej implementacji sortowania bąbelkowego potrzebne są co najmniej:

• jedna tablica — przechowuje sortowane elementy,
• dwie zmienne liczbowe sterujące pętlami — zwykle i i j, ponieważ algorytm najczęściej wykorzystuje dwie pętle zagnieżdżone,
• jedna zmienna pomocnicza — służy do zamiany miejscami dwóch elementów, np. temp.

Dlatego w pytaniu egzaminacyjnym poprawna odpowiedź to: jedna tablica, dwa liczniki pętli i jedna zmienna pomocnicza do zamiany.

Przykład w pseudokodzie

dla i od 0 do n - 2:
    dla j od 0 do n - 2 - i:
        jeżeli tablica[j] > tablica[j + 1]:
            temp = tablica[j]
            tablica[j] = tablica[j + 1]
            tablica[j + 1] = temp

Przykład w Pythonie

tab = [5, 2, 8, 1]
n = len(tab)

for i in range(n - 1):
    for j in range(n - 1 - i):
        if tab[j] > tab[j + 1]:
            temp = tab[j]
            tab[j] = tab[j + 1]
            tab[j + 1] = temp

print(tab)  # [1, 2, 5, 8]

Cechy algorytmu

• jest łatwy do zrozumienia i zapisania,
• działa wolno dla dużych zbiorów danych,
• zwykle ma złożoność czasową O(n²),
• dobrze nadaje się do nauki pętli, tablic i zamiany wartości.