Wielokrotne porównywanie sąsiednich elementów i zamiana ich miejscami. Złożoność O(n²).
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.
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ą."""
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
}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.
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.
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ść.
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.
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.
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.
Do tego hasła nie mamy jeszcze przypisanych pojedynczych zadań. Cały spis zadań maturalnych z tego działu jest tutaj:
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: