Wielokrotne porównywanie sąsiednich elementów i zamiana ich miejscami. Złożoność O(n²).
Sortowanie bąbelkowe to jeden z najprostszych algorytmów sortowania. Polega na wielokrotnym porównywaniu sąsiednich elementów tablicy i zamienianiu ich miejscami, jeśli są w nieprawidłowej kolejności.
Skąd nazwa? Większe wartości "wypływają" do końca tablicy jak bąbelki powietrza w wodzie – w każdym przebiegu największy z nieuporządkowanych elementów trafia na swoje miejsce na końcu.
Stabilność: sortowanie bąbelkowe jest algorytmem stabilnym. Zamiana następuje tylko wtedy, gdy jeden element jest ściśle większy od sąsiada, więc elementy o równych wartościach nigdy nie przeskakują jeden przez drugi i zachowują swoją pierwotną, względną kolejność.
Optymalizacja: jeżeli w całym przebiegu nie doszło do ani jednej zamiany, tablica jest już posortowana i można od razu przerwać dalsze przebiegi. To właśnie ta obserwacja odpowiada za najlepszy przypadek algorytmu (patrz sekcja „Złożoność").
Na maturze: klasyk pojawiający się w zadaniach z analizą algorytmu, liczeniem porównań i zamian. Warto znać też czas działania w różnych przypadkach.
Prześledź krok po kroku, jak algorytm porządkuje tablicę. Porównywane elementy są podświetlone, a te, które trafiły na swoje docelowe miejsce, zmieniają kolor na zielony.
Naciśnij „Krok", aby wykonać jedną operację, albo „Auto", aby uruchomić całą animację.
funkcja sortuj_babelkowo(T, n): dla i od 0 do n - 2: zamiana ← fałsz dla j od 0 do n - i - 2: jeżeli T[j] > T[j + 1]: // zamiana sąsiednich elementów pomocnicza ← T[j] T[j] ← T[j + 1] T[j + 1] ← pomocnicza zamiana ← prawda jeżeli zamiana = fałsz: przerwij // tablica posortowana zwróć T
def sortowanie_babelkowe(tablica):
"""Sortuje listę rosnąco metodą bąbelkową (in-place)."""
n = len(tablica)
for i in range(n - 1):
zamiana = False # flaga optymalizująca
# po każdym przebiegu największy element jest na końcu,
# więc zakres maleje o i
for j in range(n - i - 1):
if tablica[j] > tablica[j + 1]:
# zamiana wartości – pythonowy idiom
tablica[j], tablica[j + 1] = tablica[j + 1], tablica[j]
zamiana = True
# jeżeli nic nie zamieniono, to lista jest już posortowana
if not zamiana:
break
return tablica
# Przykład użycia
dane = [64, 25, 12, 22, 11]
print(sortowanie_babelkowe(dane))
# Wynik: [11, 12, 22, 25, 64]#include <vector>
#include <iostream>
using namespace std;
void sortowanie_babelkowe(vector<int>& t) {
int n = t.size();
for (int i = 0; i < n - 1; i++) {
bool zamiana = false;
for (int j = 0; j < n - i - 1; j++) {
if (t[j] > t[j + 1]) {
swap(t[j], t[j + 1]);
zamiana = true;
}
}
if (!zamiana) break;
}
}
int main() {
vector<int> dane = {64, 25, 12, 22, 11};
sortowanie_babelkowe(dane);
for (int x : dane) cout << x << " ";
// Wynik: 11 12 22 25 64
}O(n²)O(n)O(1)Najgorszy i średni przypadek to O(n²). Najtrudniejsza jest tablica odwrócona (posortowana malejąco) – niemal każde porównanie kończy się zamianą. Liczba porównań w kolejnych, coraz krótszych przebiegach to (n-1) + (n-2) + ... + 1, czyli w przybliżeniu n²/2. W notacji Big-O stałą ½ pomijamy, więc zostaje O(n²). Skracanie wewnętrznej pętli w każdym przebiegu przyspiesza działanie, ale nie zmienia rzędu złożoności.
Najlepszy przypadek to O(n). Dla danych już posortowanych pierwszy przebieg nie wykonuje żadnej zamiany, więc dzięki optymalizacji algorytm kończy pracę już po jednym przejściu.
Pamięć O(1). Sortujemy w miejscu, w obrębie tej samej tablicy – bez struktur pomocniczych rosnących wraz z n.
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: