Sortowanie bąbelkowe (bubble sort)

Podcast

Sortowanie Bąbelkowe: Prosty Algorytm, Wielkie Lekcje0:00 / 9:04

0:001:00 pozostało

1x

Sortowanie bąbelkowe, znane również jako bubble sort, to jeden z najprostszych algorytmów sortowania. Jego głównym celem jest uporządkowanie elementów w liście, na przykład liczb czy słów, w określonej kolejności – zazwyczaj rosnącej lub malejącej. Mimo że nie jest to najefektywniejszy algorytm dla dużych zbiorów danych, jego prostota sprawia, że jest doskonałym narzędziem do nauki podstaw algorytmiki i analizy złożoności obliczeniowej. Zrozumienie jego działania to fundament dla dalszej nauki o algorytmach.

Sortowanie Bąbelkowe (Bubble Sort) – Jak Działa?

Algorytm sortowania bąbelkowego działa na zasadzie wielokrotnego przechodzenia przez listę i porównywania sąsiednich elementów. Jeśli dwa sąsiednie elementy są w niewłaściwej kolejności, na przykład w sortowaniu rosnącym element po lewej jest większy niż po prawej, są one zamieniane miejscami. Ten proces jest powtarzany, aż cała lista zostanie posortowana.

Zasada Działania: Krok po Kroku

Nazwa „bąbelkowe” pochodzi od tego, że mniejsze (lub większe) elementy „wypływają” na początek listy, podobnie jak bąbelki powietrza w wodzie. Algorytm wykonuje serię przejść przez listę. W każdym przejściu największy (lub najmniejszy) nieposortowany element „wędruje” na swoją docelową pozycję na końcu (lub początku) nieposortowanej części listy.

Po pierwszym przejściu największy element znajdzie się na ostatniej pozycji. Po drugim przejściu drugi największy element znajdzie się na przedostatniej pozycji i tak dalej. W każdym kolejnym przejściu zakres porównywanych elementów zmniejsza się o jeden, ponieważ elementy na końcu listy są już posortowane i nie wymagają dalszych porównań.

Przykład Sortowania Bąbelkowego

Rozważmy listę liczb do posortowania rosnąco: [5, 1, 4, 2, 8]. Długość listy (n) wynosi 5.

Przejście 1:

1. Porównaj 5 i 1. 5 > 1, więc zamień: [1, 5, 4, 2, 8]
2. Porównaj 5 i 4. 5 > 4, więc zamień: [1, 4, 5, 2, 8]
3. Porównaj 5 i 2. 5 > 2, więc zamień: [1, 4, 2, 5, 8]
4. Porównaj 5 i 8. 5 < 8, nie zamieniaj: [1, 4, 2, 5, 8]

Po Przejściu 1: [1, 4, 2, 5, 8]. Element 8 jest na swojej docelowej pozycji.

Przejście 2: (Zakres porównań do przedostatniego elementu, ponieważ 8 jest już posortowane)

1. Porównaj 1 i 4. 1 < 4, nie zamieniaj: [1, 4, 2, 5, 8]
2. Porównaj 4 i 2. 4 > 2, więc zamień: [1, 2, 4, 5, 8]
3. Porównaj 4 i 5. 4 < 5, nie zamieniaj: [1, 2, 4, 5, 8]

Po Przejściu 2: [1, 2, 4, 5, 8]. Element 5 jest na swojej docelowej pozycji.

Przejście 3: (Zakres porównań do trzeciego elementu od końca)

1. Porównaj 1 i 2. 1 < 2, nie zamieniaj: [1, 2, 4, 5, 8]
2. Porównaj 2 i 4. 2 < 4, nie zamieniaj: [1, 2, 4, 5, 8]

Po Przejściu 3: [1, 2, 4, 5, 8]. Element 4 jest na swojej docelowej pozycji.

Przejście 4: (Zakres porównań do drugiego elementu od końca)

1. Porównaj 1 i 2. 1 < 2, nie zamieniaj: [1, 2, 4, 5, 8]

Po Przejściu 4: [1, 2, 4, 5, 8]. Element 2 jest na swojej docelowej pozycji. Lista jest posortowana.

Algorytm wykonał n-1 = 4 przejścia, aby posortować listę o 5 elementach.

Złożoność Obliczeniowa Sortowania Bąbelkowego

Złożoność obliczeniowa algorytmu określa, jak jego czas wykonania lub zużycie pamięci rośnie wraz ze wzrostem rozmiaru danych wejściowych (n). Jest to kluczowe dla oceny efektywności algorytmu, zwłaszcza dla dużych zbiorów danych.

Złożoność Czasowa: Najgorszy, Najlepszy i Średni Przypadek

• Najgorszy przypadek (Worst Case): Występuje, gdy lista jest posortowana w odwrotnej kolejności (np. [8, 5, 4, 2, 1]). Algorytm musi wtedy wykonać maksymalną liczbę porównań i zamian. Złożoność czasowa w najgorszym przypadku wynosi O(n²), ponieważ liczba operacji jest proporcjonalna do kwadratu liczby elementów.
• Średni przypadek (Average Case): Dla losowo ułożonych danych, złożoność czasowa również wynosi O(n²). Średnia liczba zamian jest proporcjonalna do n².
• Najlepszy przypadek (Best Case): Gdy lista jest już posortowana (np. [1, 2, 4, 5, 8]), algorytm bez optymalizacji nadal wykonuje wszystkie n-1 przejść, a w każdym przejściu n-1-i porównań. W efekcie, liczba porównań jest taka sama jak w najgorszym przypadku, czyli O(n²). Jednakże, liczba zamian wynosi 0. Zastosowanie optymalizacji, opisanej poniżej, może zredukować złożoność do O(n).

Złożoność Pamięciowa: O(1)

Sortowanie bąbelkowe jest algorytmem sortującym w miejscu (in-place). Oznacza to, że nie wymaga dodatkowej pamięci proporcjonalnej do rozmiaru danych wejściowych. Potrzebuje jedynie stałej, niewielkiej ilości pamięci na zmienne pomocnicze (np. do przechowywania tymczasowego elementu podczas zamiany). Zatem złożoność pamięciowa wynosi O(1).

Optymalizacja Algorytmu Bubble Sort

Standardowa wersja sortowania bąbelkowego zawsze wykonuje n-1 przejść, nawet jeśli lista zostanie posortowana wcześniej. Można to zoptymalizować, wprowadzając flagę (zmienną logiczną), która śledzi, czy w danym przejściu doszło do jakiejkolwiek zamiany.

Jeśli w całym przejściu nie wykonano żadnej zamiany, oznacza to, że lista jest już posortowana i algorytm może zakończyć działanie. Ta optymalizacja poprawia złożoność czasową w najlepszym przypadku do O(n), ponieważ algorytm wykona tylko jedno przejście przez już posortowaną listę, aby stwierdzić brak zamian i zakończyć pracę.

Pseudokod z Optymalizacją

Poniżej przedstawiono pseudokod sortowania bąbelkowego z optymalizacją:

funkcja sortowanie_babelkowe(lista):
 n = długość(lista)
 dla i od 0 do n-1: # Zewnętrzna pętla dla przejść
 zamieniono = Fałsz
 dla j od 0 do n-1-i: # Wewnętrzna pętla dla porównań w danym przejściu
 jeśli lista[j] > lista[j+1]:
 # Zamiana elementów
 temp = lista[j]
 lista[j] = lista[j+1]
 lista[j+1] = temp
 zamieniono = Prawda
 jeśli zamieniono jest Fałsz: # Optymalizacja: jeśli nie było zamian, lista jest posortowana
 przerwij

 zwróć lista

Implementacja w Pythonie

Implementacja sortowania bąbelkowego w języku Python z optymalizacją:

def sortowanie_babelkowe(lista):
 n = len(lista)
 for i in range(n):
 # Flaga do optymalizacji
 zamieniono = False
 # Ostatnie i elementów jest już na właściwych miejscach
 for j in range(0, n - i - 1):
 # Porównaj sąsiednie elementy
 if lista[j] > lista[j + 1]:
 # Zamień je miejscami
 lista[j], lista[j + 1] = lista[j + 1], lista[j]
 zamieniono = True
 # Jeśli w tym przejściu nie było żadnych zamian,
 # lista jest już posortowana
 if not zamieniono:
 break
 return lista

# Przykład użycia:
moja_lista = [64, 34, 25, 12, 22, 11, 90]
posortowana_lista = sortowanie_babelkowe(moja_lista)
print("Posortowana lista:", posortowana_lista) # Wynik: [11, 12, 22, 25, 34, 64, 90]

moja_lista_posortowana = [1, 2, 3, 4, 5]
posortowana_lista_opt = sortowanie_babelkowe(moja_lista_posortowana)
print("Posortowana lista (optymalizacja):", posortowana_lista_opt) # Wynik: [1, 2, 3, 4, 5]

Częste Błędy i Ważne Zrozumienie

Zrozumienie typowych pułapek i błędów związanych z sortowaniem bąbelkowym pomoże w pełnym opanowaniu tego algorytmu.

• Niezrozumienie zakresu pętli wewnętrznej: Częstym błędem jest niezmniejszanie zakresu pętli wewnętrznej (n - i - 1). Prowadzi to do niepotrzebnych porównań już posortowanych elementów na końcu listy, co obniża efektywność. Po każdym przejściu i największych elementów jest już na swoich docelowych pozycjach na końcu listy.
• Brak optymalizacji: Pominięcie flagi zamieniono sprawia, że algorytm zawsze wykonuje maksymalną liczbę przejść, nawet dla już posortowanych list. Prowadzi to do złożoności O(n²) w najlepszym przypadku, zamiast O(n).
• Mylenie z innymi algorytmami: Sortowanie bąbelkowe bywa mylone z sortowaniem przez wybieranie (selection sort) lub sortowaniem przez wstawianie (insertion sort). Chociaż wszystkie są algorytmami o złożoności O(n²), ich mechanizmy działania są różne. Sortowanie bąbelkowe koncentruje się na zamianach sąsiednich elementów, sortowanie przez wybieranie znajduje minimum, a sortowanie przez wstawianie wstawia elementy w już posortowaną część listy.
• Używanie w praktycznych zastosowaniach: Chociaż jest to świetny algorytm dydaktyczny, sortowanie bąbelkowe jest rzadko używane w praktycznych zastosowaniach dla dużych zbiorów danych ze względu na swoją niską efektywność (złożoność O(n²)). Dla większych danych preferowane są algorytmy takie jak sortowanie szybkie (quicksort) czy sortowanie przez scalanie (mergesort), które mają złożoność O(n log n).

Wizualizacja i Praktyczne Zastosowanie Sortowania Bąbelkowego

Interaktywna symulacja sortowania bąbelkowego pozwala na wizualizację każdego kroku algorytmu, co jest niezwykle pomocne w zrozumieniu jego działania.

Co można zaobserwować w symulacji

• Krokowe porównania i zamiany: Obserwuj, jak algorytm porównuje sąsiednie elementy i kiedy dochodzi do zamiany. Zobaczysz, jak mniejsze elementy stopniowo „wypływają” na początek listy, a większe „toną” na jej koniec.
• Wpływ danych wejściowych: Eksperymentuj z różnymi zestawami danych: listami posortowanymi, posortowanymi odwrotnie, losowymi oraz listami z duplikatami. Pozwala to na zrozumienie, jak układ początkowy wpływa na liczbę porównań i zamian.
• Działanie optymalizacji: W symulacji można często włączyć lub wyłączyć optymalizację. Obserwacja, jak algorytm zachowuje się na już posortowanej liście z włączoną optymalizacją (szybkie zakończenie po jednym przejściu bez zamian) i bez niej (wykonanie wszystkich przejść), doskonale ilustruje korzyści płynące z tej modyfikacji.
• Złożoność obliczeniowa w praktyce: Wizualizacja pozwala na intuicyjne zrozumienie, dlaczego złożoność czasowa wynosi O(n²). Widać, jak liczba operacji rośnie drastycznie wraz ze zwiększaniem liczby elementów, zwłaszcza w przypadku danych posortowanych odwrotnie.
• Pozycjonowanie elementów: Śledź, jak po każdym przejściu największy nieposortowany element trafia na swoje docelowe miejsce na końcu nieposortowanej części listy. To wzmacnia zrozumienie logiki działania pętli zewnętrznej i wewnętrznej.

Symulacja jest cennym narzędziem do utrwalenia wiedzy teoretycznej, umożliwiając praktyczne doświadczenie z algorytmem sortowania bąbelkowego i jego właściwościami.

FAQ: Najczęściej Zadawane Pytania o Sortowanie Bąbelkowe

Do czego służy sortowanie bąbelkowe?

Sortowanie bąbelkowe służy do porządkowania elementów w liście, np. liczb lub słów, w określonej kolejności (rosnącej lub malejącej). Jest to algorytm fundamentalny, często używany w celach edukacyjnych.

Jaka jest złożoność czasowa sortowania bąbelkowego?

W najgorszym i średnim przypadku złożoność czasowa sortowania bąbelkowego wynosi O(n²). W najlepszym przypadku, po zastosowaniu optymalizacji z flagą, złożoność spada do O(n).

Czy sortowanie bąbelkowe jest algorytmem in-place?

Tak, sortowanie bąbelkowe jest algorytmem in-place (sortującym w miejscu). Oznacza to, że do jego działania potrzebna jest jedynie stała, niewielka ilość dodatkowej pamięci (złożoność pamięciowa O(1)), niezależna od rozmiaru sortowanej listy.

Dlaczego sortowanie bąbelkowe nie jest efektywne dla dużych danych?

Sortowanie bąbelkowe ma złożoność czasową O(n²), co oznacza, że czas wykonania rośnie proporcjonalnie do kwadratu liczby elementów. Dla dużych zbiorów danych staje się to bardzo nieefektywne. Dużo lepsze algorytmy to quicksort czy mergesort, które mają złożoność O(n log n).

Czym różni się sortowanie bąbelkowe od sortowania przez wybieranie?

Sortowanie bąbelkowe zamienia sąsiednie elementy, jeśli są w niewłaściwej kolejności, sukcesywnie „wypychając” największe elementy na koniec. Sortowanie przez wybieranie natomiast w każdym kroku znajduje najmniejszy element z nieposortowanej części listy i umieszcza go na właściwej pozycji na początku posortowanej części.