Lekcja 11: Sortowanie babelkowe - algorytm i porownanie metod

Sortowanie babelkowe - zasada dzialania

Sortowanie babelkowe (ang. Bubble Sort) to jeden z najprostszych algorytmow sortowania. Polega na wielokrotnym przechodzeniu przez tablice i zamianie sasiadujacych elementow, jesli sa w zlej kolejnosci. Nazwa pochodzi od tego, ze wieksze elementy "wyplywaja" (jak babelki w wodzie) na koniec tablicy z kazdym kolejnym przejsciem. Algorytm ten jest czesto pierwszym algorytmem sortowania poznawanym na lekcjach informatyki, poniewaz jego zasada dzialania jest bardzo intuicyjna i latwa do zrozumienia nawet dla osob, ktore dopiero zaczynaja nauke programowania.

Sortowanie babelkowe nalezy do grupy algorytmow sortowania przez zamiane. W kazdym przebiegu porownywane sa kolejne pary sasiednich elementow tablicy. Jesli element na lewej pozycji jest wiekszy od elementu na prawej, nastepuje ich zamiana. Po pierwszym pelnym przebiegu najwiekszy element trafia na ostatnia pozycje tablicy. Po drugim przebiegu - drugi co do wielkosci element zajmuje swoje miejsce, i tak dalej. Proces powtarza sie az tablica bedzie calkowicie posortowana.

Algorytm - wersja podstawowa

W wersji podstawowej algorytm wykonuje dokladnie n-1 przebiegow, niezaleznie od tego, czy tablica jest juz posortowana, czy nie. W kazdym przebiegu porownuje sasiednie elementy i zamienia je, jesli sa w nieprawidlowej kolejnosci:

ALGORYTM SortowanieBabelkowe(T, n):
  DLA i OD 0 DO n-2:
    DLA j OD 0 DO n-2-i:
      JESLI T[j] > T[j+1]:
        // Zamien miejscami
        temp = T[j]
        T[j] = T[j+1]
        T[j+1] = temp

Algorytm - wersja zoptymalizowana z flaga

Wersja podstawowa ma pewna wade - wykonuje wszystkie przebiegi nawet jesli tablica jest juz posortowana. Optymalizacja polega na dodaniu zmiennej flagi, ktora sledzi, czy w danym przebiegu dokonano jakiejkolwiek zamiany. Jesli nie - tablica jest juz posortowana i mozna zakonczyc algorytm wczesniej. Ta prosta optymalizacja sprawia, ze w najlepszym przypadku (tablica juz posortowana) algorytm wykona tylko jeden przebieg, osiagajac zlozonosc O(n):

ALGORYTM SortowanieBabelkowe_Opt(T, n):
  DLA i OD 0 DO n-2:
    zamiana = FALSZ
    DLA j OD 0 DO n-2-i:
      JESLI T[j] > T[j+1]:
        temp = T[j]
        T[j] = T[j+1]
        T[j+1] = temp
        zamiana = PRAWDA
    JESLI zamiana = FALSZ:
      PRZERWIJ   // tablica juz posortowana!

Implementacja w Pythonie

Ponizej przedstawiamy implementacje sortowania babelkowego w Pythonie, wraz z wersja zoptymalizowana wykorzystujaca flage zamiany. Warto zwrocic uwage na uzycie jednoczesnego przypisania do zamiany elementow - to typowy idiom Pythona, ktory eliminuje potrzebe zmiennej tymczasowej:

def sortuj_babelkowo(lista):
    """Sortowanie babelkowe - wersja zoptymalizowana."""
    n = len(lista)
    for i in range(n - 1):
        zamiana = False
        for j in range(n - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
                zamiana = True
        if not zamiana:
            break  # tablica juz posortowana
    return lista

# Przyklad uzycia
dane = [5, 3, 8, 1, 4]
print(sortuj_babelkowo(dane))  # [1, 3, 4, 5, 8]

Przyklad krok po kroku

Tablica: [5, 3, 8, 1, 4]

Przebieg 1 (i=0):
  j=0: [5,3] -> zamien -> [3,5,8,1,4]
  j=1: [5,8] -> OK     -> [3,5,8,1,4]
  j=2: [8,1] -> zamien -> [3,5,1,8,4]
  j=3: [8,4] -> zamien -> [3,5,1,4,8]
  Najwiekszy (8) "wyplynal" na koniec!

Przebieg 2 (i=1):
  j=0: [3,5] -> OK     -> [3,5,1,4,8]
  j=1: [5,1] -> zamien -> [3,1,5,4,8]
  j=2: [5,4] -> zamien -> [3,1,4,5,8]

Przebieg 3 (i=2):
  j=0: [3,1] -> zamien -> [1,3,4,5,8]
  j=1: [3,4] -> OK     -> [1,3,4,5,8]

Przebieg 4 (i=3):
  j=0: [1,3] -> OK
  Brak zamian -> KONIEC (wersja zoptymalizowana)

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

Zlozonosc obliczeniowa

Analiza zlozonosci sortowania babelkowego pokazuje, ze nie jest to efektywny algorytm dla duzych zbiorow danych. W najgorszym i srednim przypadku algorytm wykonuje O(n^2) porownan i zamian, co czyni go niepraktycznym dla tablic o wiecej niz kilka tysiecy elementow. Jednak dzieki optymalizacji z flaga, w najlepszym przypadku (tablica juz posortowana) zlozonosc spada do O(n), co czyni go konkurencyjnym dla niemal posortowanych danych.

Porownanie: Babelkowe vs Przez wstawianie

Cecha                | Babelkowe    | Przez wstawianie
---------------------|--------------|------------------
Zlozonosc najlepsza  | O(n)         | O(n)
Zlozonosc najgorsza  | O(n^2)       | O(n^2)
Zlozonosc srednia    | O(n^2)       | O(n^2)
Stabilnosc           | TAK          | TAK
Sortowanie w miejscu | TAK          | TAK
Liczba zamian        | Duza         | Mniejsza
Wydajnosc praktyczna | Slabsza      | Lepsza
Prostota             | Bardzo prosty| Prosty