Sortowanie bąbelkowe

1. Idea algorytmu

Sortowanie bąbelkowe (bubble sort) to najprostszy algorytm sortowania. Porównuje sąsiednie elementy i zamienia je, jeśli są w złej kolejności.

Nazwa:

Większe elementy "wypływają" na górę jak bąbelki w wodzie 🫧

Wizualizacja:

Iteracja 1: [5, 3, 8, 4, 2]
           [3, 5, 8, 4, 2]  5>3, zamiana
           [3, 5, 8, 4, 2]  5<8, OK
           [3, 5, 4, 8, 2]  8>4, zamiana
           [3, 5, 4, 2, 8]  8>2, zamiana → 8 na końcu!

Iteracja 2: [3, 5, 4, 2, 8]
           [3, 5, 4, 2, 8]  3<5, OK
           [3, 4, 5, 2, 8]  5>4, zamiana
           [3, 4, 2, 5, 8]  5>2, zamiana → 5 na końcu!

Iteracja 3: [3, 4, 2, 5, 8]
           [3, 4, 2, 5, 8]  3<4, OK
           [3, 2, 4, 5, 8]  4>2, zamiana → 4 na końcu!

Iteracja 4: [3, 2, 4, 5, 8]
           [2, 3, 4, 5, 8]  3>2, zamiana → POSORTOWANE!

2. Implementacja podstawowa

Krok po kroku:

  • Zewnętrzna pętla (i): n-1 przebiegów
  • Wewnętrzna pętla (j): porównania par
  • n - i - 1: Pomijamy już posortowane elementy z końca

3. Złożoność czasowa

Najgorszy przypadek: O(n²)

Lista w odwrotnej kolejności:

Liczba porównań:

Iteracja 1: 4 porównania
Iteracja 2: 3 porównania  
Iteracja 3: 2 porównania
Iteracja 4: 1 porównanie
Razem: 4 + 3 + 2 + 1 = 10 = n(n-1)/2 = O(n²)

Najlepszy przypadek: O(n²) (bez optymalizacji!)

Lista już posortowana:

Algorytm i tak wykona wszystkie porównania! (bez optymalizacji)

Średni przypadek: O(n²)

4. Optymalizacja 1: Wczesne zakończenie

Korzyść: Najlepszy przypadek teraz O(n)!

5. Wizualizacja z printami

6. Złożoność pamięciowa: O(1)

Bubble sort jest in-place!

7. Stabilność: TAK ✅

Bubble sort jest stabilny – zachowuje kolejność równych elementów.

8. Porównanie z innymi algorytmami

9. Kiedy używać bubble sort?

✅ Używaj gdy:

  • Małe dane (n < 20)
  • Dane prawie posortowane (z optymalizacją)
  • Prostota > wydajność
  • Celów edukacyjnych

❌ Unikaj gdy:

  • Duże dane (n > 100)
  • Wydajność krytyczna
  • Przypadkowe dane

10. Warianty bubble sort

10.1. Cocktail Shaker Sort (dwukierunkowe)

10.2. Comb Sort (ulepszona wersja)

Używa większego "gap" zamiast zawsze porównywać sąsiadów.

11. Licznik porównań i zamian

12. Podsumowanie

Bubble Sort:

  • Złożoność: O(n²) średnio, O(n) najlepiej (z optymalizacją)
  • Pamięć: O(1) in-place
  • Stabilny: TAK ✅
  • Prosty: Najłatwiejszy do zrozumienia

Zalety: - Bardzo prosty - Stabilny - In-place (O(1) pamięci) - Adaptywny (z optymalizacją)

Wady: - BARDZO wolny dla dużych danych (O(n²)) - Nie używany w praktyce - Dużo niepotrzebnych porównań

Kluczowa optymalizacja:

Kiedy używać:

  • Edukacja – najlepszy do nauki
  • Małe dane (< 20 elementów)
  • Prawie posortowane dane

W praktyce:

❌ NIE używaj bubble sort dla produkcji – użyj sorted() lub quick/merge sort!

Co dalej warto poznać:

  • Selection Sort (podobna idea)
  • Insertion Sort (lepsza dla małych danych)
  • Quick Sort (praktyczny wybór)
Wróć do spisu lekcji