Sortowanie bąbelkowe w Pythonie i C++

Sortowanie bąbelkowe (ang. bubble sort) to najbardziej znany prosty algorytm sortowania. Porównuje tylko sąsiednie elementy i zamienia je, gdy stoją w złej kolejności. Duże wartości przesuwają się przy tym w prawo, aż na koniec listy, jak bąbelki powietrza wypływające na powierzchnię wody. Stąd nazwa.

Na tej stronie znajdziesz ideę algorytmu, kod w Pythonie i C++, tabelę przebiegów, wersję z flagą, liczenie zamian oraz porównanie z sortowaniem przez wybieranie i przez wstawianie. Każdy przykład przejdziesz krok po kroku w kursie Algorytmy z podstawy programowej: w przeglądarce, bez instalowania niczego i bez konta, z podglądem zmiennych w każdym kroku.

Przejdź sortowanie bąbelkowe krok po kroku

Idea: porównuj sąsiadów

Jeden przebieg sortowania bąbelkowego to przejście po liście od lewej do prawej:

1. Porównaj element j z elementem j + 1.
2. Jeśli lewy jest większy od prawego, zamień je.
3. Przesuń się o jedno miejsce w prawo i powtórz.

Największy element, raz “złapany”, jest przesuwany przy każdym porównaniu, więc po pierwszym przebiegu na pewno stoi na końcu. Po drugim przebiegu drugi największy stoi przed nim. Koniec listy jest więc z każdym przebiegiem coraz dłuższy i posortowany, dlatego wewnętrzna pętla może być w przebiegu i o i krótsza: range(n - 1 - i).

Sortowanie bąbelkowe w Pythonie

dane = [5, 1, 4, 2, 8]
n = len(dane)
for i in range(n - 1):
    for j in range(n - 1 - i):
        if dane[j] > dane[j + 1]:
            dane[j], dane[j + 1] = dane[j + 1], dane[j]
    print("przebieg", i + 1, dane)

przebieg 1 [1, 4, 2, 5, 8]
przebieg 2 [1, 2, 4, 5, 8]
przebieg 3 [1, 2, 4, 5, 8]
przebieg 4 [1, 2, 4, 5, 8]

Zamiana dane[j], dane[j + 1] = dane[j + 1], dane[j] to w Pythonie jedno przypisanie krotki, bez zmiennej pomocniczej.

Tabela przebiegów

Rozpiszmy porównania dwóch pierwszych przebiegów dla listy [5, 1, 4, 2, 8]:

Po drugim przebiegu lista jest już posortowana, a mimo to program wykonał jeszcze dwa przebiegi (3 i 4), w których nie było ani jednej zamiany. To strata czasu, którą usuwa flaga.

Wersja z flagą: koniec, gdy nie było zamian

Jeśli w całym przebiegu nic nie zamieniliśmy, lista jest posortowana. Zmienna zamiana zapamiętuje, czy w przebiegu była zamiana, a break kończy pętlę:

def babelkowe(dane):
    n = len(dane)
    przebiegi = 0
    for i in range(n - 1):
        zamiana = False
        przebiegi += 1
        for j in range(n - 1 - i):
            if dane[j] > dane[j + 1]:
                dane[j], dane[j + 1] = dane[j + 1], dane[j]
                zamiana = True
        if not zamiana:
            break
    return przebiegi


lista = [1, 2, 3, 5, 4, 6, 7, 8]
print(babelkowe(lista), lista)
lista = [8, 7, 6, 5, 4, 3, 2, 1]
print(babelkowe(lista), lista)

2 [1, 2, 3, 4, 5, 6, 7, 8]
7 [1, 2, 3, 4, 5, 6, 7, 8]

Dla listy prawie posortowanej wystarczyły dwa przebiegi zamiast siedmiu: w drugim nie było zamian, więc algorytm przerwał pracę. Dla listy odwróconej flaga nic nie daje, potrzebne jest wszystkie 7 przebiegów.

Krokuj wersję z flagą

Sortowanie bąbelkowe w C++

W C++ tablicę przekazujemy do funkcji razem z rozmiarem, zamianę piszemy przez zmienną pomocniczą, a flaga jest typu bool:

#include <iostream>
using namespace std;

void babelkowe(int t[], int n) {
  for (int i = 0; i < n - 1; i++) {
    bool zamiana = false;
    for (int j = 0; j < n - 1 - i; j++) {
      if (t[j] > t[j + 1]) {
        int tmp = t[j];
        t[j] = t[j + 1];
        t[j + 1] = tmp;
        zamiana = true;
      }
    }
    if (!zamiana) {
      break;
    }
  }
}

int main() {
  int t[5] = {5, 1, 4, 2, 8};
  babelkowe(t, 5);
  for (int i = 0; i < 5; i++) {
    cout << t[i] << endl;
  }
  return 0;
}

1
2
4
5
8

Liczba zamian w sortowaniu bąbelkowym jest równa liczbie inwersji, czyli par elementów ustawionych w złej kolejności. Lista {3, 1, 2, 5, 4} ma trzy inwersje: (3, 1), (3, 2) i (5, 4). Sprawdźmy licznikiem:

#include <iostream>
using namespace std;

int main() {
  int t[5] = {3, 1, 2, 5, 4};
  int n = 5;
  int zamiany = 0;
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - 1 - i; j++) {
      if (t[j] > t[j + 1]) {
        int tmp = t[j];
        t[j] = t[j + 1];
        t[j + 1] = tmp;
        zamiany++;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    if (i > 0) {
      cout << " ";
    }
    cout << t[i];
  }
  cout << endl;
  cout << "zamiany: " << zamiany << endl;
  return 0;
}

1 2 3 4 5
zamiany: 3

Sortowanie malejąco to zmiana jednego znaku: > w porównaniu na <.

Złożoność i porównanie z innymi sortowaniami

Sortowanie bąbelkowe ma złożoność O(n²) w przypadku pesymistycznym i średnim oraz O(1) pamięci dodatkowej. Dla listy odwróconej każda para jest inwersją, więc algorytm wykonuje n(n-1)/2 porównań i tyle samo zamian. Wersja z flagą dla listy posortowanej kończy po jednym przebiegu: O(n).

Tabela pokazuje liczbę porównań i zamian (dla wstawiania: przesunięć) dla list 8-elementowych; sortowanie bąbelkowe w wersji z flagą:

Bąbelkowe i sortowanie przez wstawianie wykonują tyle samo zamian lub przesunięć (oba usuwają po jednej inwersji naraz), ale wstawianie zwykle potrzebuje mniej porównań. Jedno przesunięcie przy wstawianiu to też tylko jedno przypisanie, a zamiana sąsiadów to trzy. Sortowanie przez wybieranie zawsze porównuje tyle samo razy, za to zamienia najmniej. Sortowanie bąbelkowe jest najprostsze do zapamiętania, ale w praktyce zwykle najwolniejsze z tej trójki.

Lista kroków, pseudokod i schemat blokowy

Podstawa programowa wymaga, żeby uczeń opisywał problem specyfikacją (dane i wynik) i zapisywał algorytm listą kroków albo pseudokodem, a w szkole rysuje się też schematy blokowe. Pseudokod jest w stylu arkuszy maturalnych: ← to przypisanie, div i mod to iloraz i reszta z dzielenia całkowitego, a elementy tablic i znaki napisów są numerowane od 1 (w Pythonie od 0). Te same zapisy są w kursie przy lekcjach tematu, pod przyciskiem Algorytm.

Sortowanie bąbelkowe

Specyfikacja. Dane: tablica T[1..n]. Wynik: tablica T posortowana rosnąco.

Lista kroków:

1. Wczytaj n i tablicę T[1..n]. Ustaw i = 1.
2. Jeśli i = n, wypisz T i zakończ.
3. Dla j = 1, 2, …, n - i: jeśli T[j] > T[j + 1], zamień te dwa elementy miejscami.
4. Zwiększ i o 1 i wróć do kroku 2.

Pseudokod:

wczytaj n, T
dla i = 1, 2, ..., n - 1 wykonuj
  dla j = 1, 2, ..., n - i wykonuj
    jeżeli T[j] > T[j + 1] to
      zamień T[j] z T[j + 1]
wypisz T

Schemat blokowy:

Drzewo decyzyjne sortowania trzech liczb. Drzewo pokazuje wszystkie możliwe przebiegi algorytmu dla trzech różnych liczb a, b, c ułożonych w tablicy w tej kolejności. Każdy węzeł to porównanie wykonane przez algorytm, a liść to ustalona kolejność od najmniejszej liczby. Algorytm wykonuje 3 porównania. Węzeł z jedną gałęzią to porównanie, którego wynik wynika już z wcześniejszych porównań: algorytm i tak je wykonuje.

Najczęstsze błędy

• Wyjście poza listę. Pętla for j in range(n) dochodzi do j = n - 1, a wtedy dane[j + 1] nie istnieje: Python zgłasza IndexError, a C++ czyta pamięć za tablicą. Wewnętrzna pętla kończy się na n - 1 - i.
• Jeden przebieg zamiast wielu. Pojedyncze przejście ustawia na miejscu tylko największy element. Potrzebna jest zewnętrzna pętla.
• Flaga ustawiona poza pętlą przebiegów. zamiana = False musi być na początku każdego przebiegu, inaczej po pierwszej zamianie zostaje True na zawsze i break nigdy nie zadziała.
• Warunek >= zamiast >. Sortowanie nadal działa, ale zamienia równe elementy (więcej pracy) i przestaje być stabilne.
• Zamiana w C++ bez zmiennej pomocniczej. t[j] = t[j + 1]; t[j + 1] = t[j]; gubi jedną wartość. Potrzebna jest zmienna tmp.

Ćwicz w przeglądarce

W temacie “Sortowanie bąbelkowe” kursu Algorytmy z podstawy programowej czekają dwa przykłady do krokowania i trzy zadania, które sprawdzają się automatycznie po uruchomieniu:

• sortowanie bąbelkowe rosnąco (własna funkcja, bez sort() i sorted()),
• ile zamian wykona sortowanie bąbelkowe (liczenie inwersji),
• sortowanie bąbelkowe malejąco.

Przycisk Krok wykonuje jedną linię, a panel obok pokazuje aktualne wartości i, j, flagi i całej listy, więc widać, jak duży element wędruje w prawo. W wersji z funkcją Krok wchodzi do jej środka, a stos wywołań pokazuje, skąd została wywołana. Dalsze algorytmy z tego samego kursu: wyszukiwanie liniowe i binarne oraz algorytm Euklidesa. Pełna lista: algorytmy z podstawy programowej.

Dla nauczycieli

Sortowanie bąbelkowe dobrze nadaje się do lekcji “na sucho”: uczniowie mogą odegrać je, stając w rzędzie i zamieniając się z sąsiadem, a potem porównać to z programem krokowanym na rzutniku. Wersja z flagą to naturalny przykład optymalizacji, którą da się zmierzyć licznikiem przebiegów. W BitWizards przydzielasz kurs klasie, udostępniasz tematy stopniowo i widzisz przebieg pisania kodu każdego ucznia (podgląd na żywo i odtwarzanie historii). Platforma jest darmowa dla szkół - jak zacząć. Więcej o tym, gdzie algorytmy leżą w podstawie programowej: informatyka w szkole.