Sortowanie bąbelkowe
Wielokrotne porównywanie sąsiednich elementów i zamiana ich miejscami. Złożoność O(n²).
Opis
Sortowanie bąbelkowe to najprostszy sposób, żeby ułożyć liczby po kolei. Przechodzisz przez tablicę i porównujesz dwa sąsiednie elementy. Jeśli stoją w złej kolejności – zamieniasz je miejscami. Powtarzasz to od początku tak długo, aż nie trzeba już nic zamieniać.
Skąd nazwa? Największe liczby powoli „wypływają" na koniec tablicy, tak jak bąbelki powietrza na powierzchnię wody. Po każdym przejściu kolejna największa liczba stoi już na swoim miejscu na końcu.
Mała sztuczka: jeśli podczas całego przejścia ani razu nic nie zamieniłeś, to znaczy, że tablica jest już ułożona – i można od razu skończyć, bez kolejnych przejść.
Na maturze: zwykle nie chodzi o napisanie kodu, tylko o policzenie, ile razy coś porównano albo zamieniono dla podanej tablicy.
Wizualizacja
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ę.
Pseudokod
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
Implementacja w Pythonie i C++
def sortowanie_babelkowe(tablica):
"""Sortuje listę rosnąco metodą bąbelkową."""
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
}Najczęściej zadawane pytania
Czym różni się przebieg od zamiany?
Przebieg to jeden pełny przejazd pętli zewnętrznej przez tablicę. W jednym przebiegu może dojść do wielu zamian sąsiednich elementów albo do żadnej – i to liczba zamian, nie przebiegów, mówi o „bałaganie" w danych.
Dlaczego wewnętrzna pętla jest coraz krótsza?
Po każdym przebiegu największy z nieuporządkowanych elementów trafia na swoje miejsce na końcu, więc w kolejnym przebiegu nie trzeba go już sprawdzać. Stąd zakres skraca się o i i w pseudokodzie wygląda jak n - i - 2.
Czy sortowanie bąbelkowe jest stabilne?
Tak. Zamieniamy tylko wtedy, gdy element jest ściśle większy od sąsiada (>, nie >=), więc elementy o równych wartościach nigdy nie przeskakują przez siebie i zachowują swoją pierwotną kolejność.
Kiedy bąbelkowe działa w czasie O(n)?
Gdy tablica jest już posortowana, a algorytm ma optymalizację z flagą zamiany: pierwszy przebieg nie wykonuje żadnej zamiany, flaga zostaje fałsz i pętla kończy się po jednym przejściu.
Ćwiczenie
Prześledź sortowanie bąbelkowe tablicy [5, 1, 4, 2] (rosnąco) i uzupełnij pola, potem kliknij Sprawdź.
Stan tablicy po pierwszym przebiegu to , a liczba zamian w tym przebiegu wynosi .
Po pierwszym przebiegu na swoim docelowym miejscu (na końcu) stoi już element – największy z całej tablicy.
Uzupełnij zdania o własnościach algorytmu:
| Własność | Odpowiedź |
|---|---|
| Złożoność w najgorszym przypadku | |
| Złożoność pamięciowa | |
| Czy jest stabilne? |
Zamiana dwóch sąsiednich elementów wymaga zmiennej , chyba że język pozwala przypisać obie wartości naraz.
Złożoność obliczeniowa
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.
Przećwicz w zadaniach maturalnych
Do tego hasła nie mamy jeszcze przypisanych pojedynczych zadań. Cały spis zadań maturalnych z tego działu jest tutaj:
Powiązane zagadnienia
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: