Liceum Klasa I 45 minut PP: I.2c | s. 342

Lekcja 20: Sortowanie babelkowe - algorytm i implementacja

Zasada dzialania bubble sort, zamiana par, implementacja w Pythonie, optymalizacja z flaga, zlozonosc obliczeniowa

📋 Podstawa programowa: I.2c
algorytmybubble sortimplementacjasortowanie babelkowezlozonosc
00:00
Wprowadzenie
5 min
00:05
Teoria
15 min
00:20
Cwiczenia
15 min
00:35
Podsumowanie
10 min
📚

Teoria

▼

Czym jest sortowanie babelkowe?

Sortowanie babelkowe (ang. bubble sort) to jeden z najprostszych algorytmow sortowania. Nazwa pochodzi od sposobu, w jaki wieksze elementy "wyplywaja" na koniec tablicy - jak babelki powietrza w wodzie unoszace sie ku gorze.

Algorytm wielokrotnie przechodzi przez tablice, porownujac sasiednie pary elementow i zamieniajac je miejscami, jesli sa w zlej kolejnosci. Przejscia powtarzamy az do momentu, gdy tablica jest posortowana.

Zasada dzialania: Porownuj kolejne pary sasiednich elementow. Jesli lewy jest wiekszy od prawego - zamien je miejscami. Powtarzaj przejscia przez tablice, az w zadnym przejsciu nie nastapi zamiana.

Wizualizacja krok po kroku

Posortujmy tablice [5, 3, 8, 1, 6] algorytmem bubble sort:

Tablica poczatkowa: [5, 3, 8, 1, 6]

=== Przejscie 1 ===
  [5, 3, 8, 1, 6]  ->  5>3? TAK, zamiana  ->  [3, 5, 8, 1, 6]
  [3, 5, 8, 1, 6]  ->  5>8? NIE           ->  [3, 5, 8, 1, 6]
  [3, 5, 8, 1, 6]  ->  8>1? TAK, zamiana  ->  [3, 5, 1, 8, 6]
  [3, 5, 1, 8, 6]  ->  8>6? TAK, zamiana  ->  [3, 5, 1, 6, 8]
  Po przejsciu 1: [3, 5, 1, 6, 8]  (8 "wyplynelo" na koniec)

=== Przejscie 2 ===
  [3, 5, 1, 6, 8]  ->  3>5? NIE           ->  [3, 5, 1, 6, 8]
  [3, 5, 1, 6, 8]  ->  5>1? TAK, zamiana  ->  [3, 1, 5, 6, 8]
  [3, 1, 5, 6, 8]  ->  5>6? NIE           ->  [3, 1, 5, 6, 8]
  Po przejsciu 2: [3, 1, 5, 6, 8]  (6 na swoim miejscu)

=== Przejscie 3 ===
  [3, 1, 5, 6, 8]  ->  3>1? TAK, zamiana  ->  [1, 3, 5, 6, 8]
  [1, 3, 5, 6, 8]  ->  3>5? NIE           ->  [1, 3, 5, 6, 8]
  Po przejsciu 3: [1, 3, 5, 6, 8]  (5 na swoim miejscu)

=== Przejscie 4 ===
  [1, 3, 5, 6, 8]  ->  1>3? NIE           ->  [1, 3, 5, 6, 8]
  Brak zamian - tablica posortowana!

Wynik: [1, 3, 5, 6, 8]

Podstawowa implementacja w Pythonie

def bubble_sort(tablica):
    """Sortowanie babelkowe - wersja podstawowa."""
    n = len(tablica)

    for i in range(n - 1):
        # Kazde przejscie "wyplywa" najwiekszy element na koniec
        for j in range(n - 1 - i):
            if tablica[j] > tablica[j + 1]:
                # Zamiana sasiednich elementow
                tablica[j], tablica[j + 1] = tablica[j + 1], tablica[j]

    return tablica

# Przyklad uzycia
dane = [5, 3, 8, 1, 6]
print(f"Przed: {dane}")
bubble_sort(dane)
print(f"Po:    {dane}")
# Przed: [5, 3, 8, 1, 6]
# Po:    [1, 3, 5, 6, 8]

Optymalizacja z flaga (early exit)

Podstawowa wersja bubble sort zawsze wykonuje n-1 przejsc, nawet jesli tablica jest juz posortowana. Mozemy to zoptymalizowac dodajac flage, ktora sprawdza, czy w danym przejsciu nastapila jakakolwiek zamiana. Jesli nie - tablica jest posortowana i mozemy zakonczyc wczesniej:

def bubble_sort_optimized(tablica):
    """Sortowanie babelkowe z optymalizacja - wczesne zakonczenie."""
    n = len(tablica)

    for i in range(n - 1):
        zamiana = False  # flaga: czy byla zamiana?

        for j in range(n - 1 - i):
            if tablica[j] > tablica[j + 1]:
                tablica[j], tablica[j + 1] = tablica[j + 1], tablica[j]
                zamiana = True

        # Jesli nie bylo zadnej zamiany - tablica posortowana!
        if not zamiana:
            print(f"Zakonczono wczesniej po {i + 1} przejsciach")
            break

    return tablica

# Test na tablicy prawie posortowanej
dane = [1, 2, 3, 5, 4]
print(f"Przed: {dane}")
bubble_sort_optimized(dane)
print(f"Po:    {dane}")
# Zakonczono wczesniej po 2 przejsciach

Wersja z wypisywaniem krokow

def bubble_sort_verbose(tablica):
    """Wersja z wypisywaniem stanu po kazdym przejsciu."""
    n = len(tablica)
    print(f"Start: {tablica}")

    for i in range(n - 1):
        zamiana = False
        for j in range(n - 1 - i):
            if tablica[j] > tablica[j + 1]:
                tablica[j], tablica[j + 1] = tablica[j + 1], tablica[j]
                zamiana = True
        print(f"Przejscie {i + 1}: {tablica}")
        if not zamiana:
            break

    return tablica

# Test
bubble_sort_verbose([5, 3, 8, 1, 6])

Zlozonosc obliczeniowa

Analiza zlozonosci algorytmu sortowania babelkowego:

  • Najgorszy przypadek O(n²) - gdy tablica jest posortowana malejaco. Wymaga maksymalnej liczby porownan i zamian.
  • Najlepszy przypadek O(n) - gdy tablica jest juz posortowana (z optymalizacja flagi). Jedno przejscie bez zamian konczy algorytm.
  • Sredni przypadek O(n²) - dla losowych danych wymaga srednio n²/4 zamian.
  • Zlozonosc pamieciowa O(1) - algorytm sortuje w miejscu (in-place).
Porownanie bubble sort vs insertion sort: Oba algorytmy maja zlozonosc O(n²), ale w praktyce insertion sort jest szybszy, poniewaz wykonuje mniej operacji zamiany. Bubble sort w najgorszym przypadku wymaga n²/2 zamian, podczas gdy insertion sort wymaga n²/2 przesuniec (co jest szybsze niz zamiana dwoch elementow).
Wazne: Sortowanie babelkowe jest jednym z najwolniejszych algorytmow sortowania i w praktyce niemal nigdy nie jest uzywane w profesjonalnym oprogramowaniu. Jest jednak doskonalym narzedziem dydaktycznym do nauki koncepcji sortowania, poniewaz jego zasada dzialania jest bardzo prosta i intuicyjna.
✏️

Zadania

▼
Latwe

Zadanie 1: Reczne sortowanie babelkowe

Posortuj recznie (na kartce) tablice [4, 7, 2, 9, 1] algorytmem bubble sort. Zapisz stan tablicy po kazdym pelnym przejsciu. Ile przejsc potrzeba? Zweryfikuj w programie.

Pokaz rozwiazanie 
# Reczne sortowanie [4, 7, 2, 9, 1]:
# Przejscie 1: [4,7,2,9,1] -> [4,2,7,1,9] (zamiana: 7-2, 9-1; 9 na koncu)
# Przejscie 2: [4,2,7,1,9] -> [2,4,1,7,9] (zamiana: 4-2, 7-1; 7 na miejscu)
# Przejscie 3: [2,4,1,7,9] -> [2,1,4,7,9] (zamiana: 4-1; 4 na miejscu)
# Przejscie 4: [2,1,4,7,9] -> [1,2,4,7,9] (zamiana: 2-1; gotowe!)

# Weryfikacja w Pythonie:
def bubble_sort_verbose(tab):
    n = len(tab)
    for i in range(n - 1):
        zamiana = False
        for j in range(n - 1 - i):
            if tab[j] > tab[j + 1]:
                tab[j], tab[j + 1] = tab[j + 1], tab[j]
                zamiana = True
        print(f"Przejscie {i + 1}: {tab}")
        if not zamiana:
            break

bubble_sort_verbose([4, 7, 2, 9, 1])
Srednie

Zadanie 2: Implementacja z flaga early exit

Napisz bubble sort z optymalizacja wczesnego zakonczenia (flaga). Przetestuj na tablicy juz posortowanej [1, 2, 3, 4, 5] i sprawdz, ile przejsc wykona algorytm. Porownaj z wersja bez flagi.

Pokaz rozwiazanie 
def bubble_bez_flagi(tab):
    """Wersja BEZ optymalizacji."""
    n = len(tab)
    przejscia = 0
    for i in range(n - 1):
        przejscia += 1
        for j in range(n - 1 - i):
            if tab[j] > tab[j + 1]:
                tab[j], tab[j + 1] = tab[j + 1], tab[j]
    return przejscia

def bubble_z_flaga(tab):
    """Wersja Z optymalizacja."""
    n = len(tab)
    przejscia = 0
    for i in range(n - 1):
        przejscia += 1
        zamiana = False
        for j in range(n - 1 - i):
            if tab[j] > tab[j + 1]:
                tab[j], tab[j + 1] = tab[j + 1], tab[j]
                zamiana = True
        if not zamiana:
            break
    return przejscia

# Test na posortowanej tablicy
tab1 = [1, 2, 3, 4, 5]
tab2 = [1, 2, 3, 4, 5]

p1 = bubble_bez_flagi(tab1)
p2 = bubble_z_flaga(tab2)

print(f"Bez flagi: {p1} przejsc")   # 4 przejscia
print(f"Z flaga:   {p2} przejsc")   # 1 przejscie!
Srednie

Zadanie 3: Sortowanie malejace i sortowanie tekstow

Zmodyfikuj bubble sort tak, aby sortowal: (a) liczby malejaco, (b) liste imion alfabetycznie. Przetestuj na przykladowych danych.

Pokaz rozwiazanie 
def bubble_sort_custom(tablica, malejaco=False):
    """Bubble sort z wyborem kierunku sortowania."""
    n = len(tablica)
    for i in range(n - 1):
        zamiana = False
        for j in range(n - 1 - i):
            if malejaco:
                warunek = tablica[j] < tablica[j + 1]
            else:
                warunek = tablica[j] > tablica[j + 1]
            if warunek:
                tablica[j], tablica[j + 1] = tablica[j + 1], tablica[j]
                zamiana = True
        if not zamiana:
            break
    return tablica

# a) Liczby malejaco
liczby = [3, 7, 1, 9, 4]
print(f"Malejaco: {bubble_sort_custom(liczby[:], malejaco=True)}")
# [9, 7, 4, 3, 1]

# b) Imiona alfabetycznie
imiona = ["Zofia", "Anna", "Marek", "Jan", "Ewa"]
print(f"Imiona:  {bubble_sort_custom(imiona[:])}")
# ['Anna', 'Ewa', 'Jan', 'Marek', 'Zofia']
Trudne

Zadanie 4: Porownanie metod sortowania - analiza czasowa

Napisz program, ktory porownuje czas dzialania trzech algorytmow: bubble sort (podstawowy), bubble sort (z flaga) i insertion sort. Przetestuj na losowych tablicach o rozmiarach 1000, 2000 i 5000 elementow. Wyswietl wyniki w tabeli.

Pokaz rozwiazanie 
import random
import time

def bubble_basic(tab):
    n = len(tab)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if tab[j] > tab[j + 1]:
                tab[j], tab[j + 1] = tab[j + 1], tab[j]

def bubble_flag(tab):
    n = len(tab)
    for i in range(n - 1):
        zamiana = False
        for j in range(n - 1 - i):
            if tab[j] > tab[j + 1]:
                tab[j], tab[j + 1] = tab[j + 1], tab[j]
                zamiana = True
        if not zamiana:
            break

def insertion(tab):
    for i in range(1, len(tab)):
        klucz = tab[i]
        j = i - 1
        while j >= 0 and tab[j] > klucz:
            tab[j + 1] = tab[j]
            j -= 1
        tab[j + 1] = klucz

def mierz_czas(funkcja, tablica):
    kopia = tablica[:]
    start = time.time()
    funkcja(kopia)
    return time.time() - start

# Porownanie
print(f"{'Rozmiar':>8} | {'Bubble':>10} | {'Bubble+flaga':>12} | {'Insertion':>10}")
print("-" * 50)

for rozmiar in [1000, 2000, 5000]:
    dane = [random.randint(1, 10000) for _ in range(rozmiar)]
    t1 = mierz_czas(bubble_basic, dane)
    t2 = mierz_czas(bubble_flag, dane)
    t3 = mierz_czas(insertion, dane)
    print(f"{rozmiar:>8} | {t1:>9.4f}s | {t2:>11.4f}s | {t3:>9.4f}s")
🎥

Materialy wideo

▼
Bubble Sort + Optymalizacja (JavaScript) - Prosty algorytm sortowania
Paweł Długosz
Algorytmy - Bubble Sort, Sortowane bąbelkowe implementacja
kakaboc
🎧

Podcasty

▼
✔️

Quiz - sprawdz sie!

▼
📜

Podstawa programowa

▼
← Lekcja 19: Sortowanie przez wstawianie Lekcja 21: Ciag Fibonacciego →