Sortowanie bąbelkowe: jak działa algorytm i jak go zapisać

Na czym polega sortowanie bąbelkowe

Polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona porządek, w jakim sortuje się tablicę. Cały algorytm to dwie zagnieżdżone pętle:

1. Przejdź listę od początku, porównując każdą parę sąsiadów.
2. Jeśli lewy element jest większy od prawego (przy sortowaniu rosnącym), zamień je miejscami.
3. Po przejściu całej listy największy element jest na końcu, więc kolejny przebieg może go pominąć.
4. Powtarzaj, aż lista będzie posortowana.

Pseudokod:

dla i od 1 do n-1:
    dla j od 1 do n-i:
        jeśli lista[j] > lista[j+1]:
            zamień lista[j] z lista[j+1]

Przykład krok po kroku

Weź listę [5, 1, 4, 2, 8] i posortuj ją rosnąco.

• Przebieg 1. Porównania: (5, 1) zamiana, (5, 4) zamiana, (5, 2) zamiana, (5, 8) bez zamiany. Piątka „przepłynęła” w prawo, a 8 już stoi na końcu.
• Przebieg 2. Ostatni element jest na swoim miejscu, więc porównujesz trzy pary: (1, 4) bez zamiany, (4, 2) zamiana, (4, 5) bez zamiany.
• Przebieg 3. Dwa porównania, (1, 2) i (2, 4), i żadnej zamiany. Brak zamian oznacza, że lista jest posortowana.

Razem wyszło 9 porównań i 4 zamiany.

Kod w Pythonie z flagą zamiany

Podstawowa wersja zawsze wykonuje wszystkie przebiegi. Prosta optymalizacja to flaga informująca, czy w danym przebiegu doszło do zamiany: jeśli nie, lista jest już posortowana i pętlę można przerwać.

def bubble_sort(lista):
    n = len(lista)
    for i in range(n - 1):
        zamiana = False
        for j in range(n - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
                zamiana = True
        print(f"Przebieg {i + 1}: {lista}")
        if not zamiana:
            break

dane = [5, 1, 4, 2, 8]
bubble_sort(dane)
print("Wynik:", dane)

Wynik uruchomienia w Pythonie 3.13:

Przebieg 1: [1, 4, 2, 5, 8]
Przebieg 2: [1, 2, 4, 5, 8]
Przebieg 3: [1, 2, 4, 5, 8]
Wynik: [1, 2, 4, 5, 8]

Wypisane listy zgadzają się z tabelą przebiegów. Zakres wewnętrznej pętli range(n - 1 - i) skraca się z każdym przebiegiem, bo ostatnie i elementów jest już na miejscu. Flaga wydłuża wprawdzie pojedynczy przebieg (trzeba ją wyzerować, ustawić i sprawdzić), ale na liście już posortowanej wystarczy jeden przebieg: bubble_sort([1, 2, 3, 4, 5]) kończy po pierwszym wypisaniu, bo nie zaszła żadna zamiana.

Złożoność i stabilność

Dla listy o n elementach algorytm wykonuje do n − 1 przebiegów, a w każdym kolejnym o jedno porównanie mniej. W sumie daje to rzędu n² porównań, czyli złożoność czasową O(n²). Bez flagi dzieje się tak dla każdego układu danych; z flagą lista już posortowana kończy się po jednym przebiegu (rzędu n porównań). Pamięć dodatkowa to O(1): potrzebna jest tylko zmienna na zamianę i flaga. Sortowanie bąbelkowe jest stabilne, czyli nie zmienia względnej kolejności elementów o równych kluczach, o ile zamieniasz tylko wtedy, gdy lewy element jest ściśle większy od prawego (znak >, nie >=).

Przy podwojeniu liczby elementów liczba porównań rośnie mniej więcej czterokrotnie. Dla kilkudziesięciu elementów różnica jest niewidoczna, dla setek tysięcy staje się wyraźna.

Porównanie z innymi metodami sortowania

Sortowanie przez wstawianie ma ten sam rząd złożoności co bąbelkowe, ale na ogół działa szybciej i jest równie proste, dlatego to ono częściej pojawia się w praktyce i podręcznikach. Metody O(n log n) są dla dużych zbiorów znacznie szybsze. Na co dzień nie pisze się własnego sortowania: wbudowane sorted() i list.sort() w Pythonie korzystają z gotowego, wydajnego algorytmu.

Zobacz też: Schemat blokowy, Matura z informatyki.