Sortowanie bąbelkowe (bubble sort) – na czym polega, przykład i schemat blokowy

Sortowanie jest stosowane w rozmaitych aplikacjach oraz algorytmach. Oczywiście zależnie od danych czy oczekiwanej wydajności, używa się rozmaitych rozwiązań. Naukę zasad sortowania najczęściej zaczyna się od sortowania bąbelkowego, ze względu na jego prostotę.

Na czym polega sortowanie bąbelkowe?

Sortowanie bąbelkowe porównuje sąsiadujące ze sobą elementy, wielokrotnie przechodząc przez listę danych. To jeden z najprostszych algorytmów sortujących, umożliwiający posortowanie wartości malejąco lub rosnąco.

W trakcie kolejnych cykli algorytmu porównywane są ze sobą dwie liczby znajdujące się obok siebie. Ta z nich, która jest większa lub mniejsza (zależnie czy sortowanie jest rosnące czy też malejące) zostaje przesunięta w prawą stronę. Algorytm kończy się, gdy wszystkie wartości zostaną ułożone w odpowiedniej kolejności.

Należy pamiętać, że ten algorytm nie jest zbyt dobrym wyborem, jeżeli zamierzasz posortować duże ilości danych.

Jak działa sortowanie bąbelkowe – Przykład

Z pomocą algorytmu sortowania bąbelkowego, posortowana rosnąco zostanie lista danych złożona z liczb 1, 3, 2, 6, 2. Zaczynając od lewej strony, porównywane będą ze sobą po dwie kolejne wartości

Poniżej znajduje się analiza działania tego algorytmu rosnąco dla n = 5. Początkowa lista (tablica) prezentuje się tak:

1 3 2 6 2

Działanie algorytmu rozpoczyna się od pierwszej liczby po lewej.

1 3 2 6 2

(1 3) 2 6 2 – w nawiasach znajdują się porównywane liczby

1 3 2 6 2

Porównywana jest z wartością po prawej, a więc 3. Skoro wartość po prawej jest większa, liczba nie ulega przemieszczeniu.

1 3 2 6 2

1 (3 2) 6 2

1 2 3 6 2

W takim przypadku bierze się pod uwagę kolejną liczbę po prawej, w tym przypadku 3, którą porównuje się z 2. Wartość po prawej jest mniejsza, więc ulegają zamianie.

1 2 3 6 2

1 2 (3 6) 2

1 2 3 6 2

Teraz porównanie wykazuje, że kolejna wartość jest większa.

1 2 3 6 2

1 2 3 (6 2)

1 2 3 2 6

Kolejna zamiana.

W tym momencie następuje kolejny cykl sortowania.

1 2 3 2 6

(1 2) 3 2 6

1 2 3 2 6

1 (2 3) 2 6

1 2 3 2 6

1 2 (3 2) 6

1 2 2 3 6

Zamiana liczb następuje, skoro 3 jest większe od 2 (wartości po prawej).

1 2 2 3 6

Teraz druga pętla się kończy i rozpoczyna się trzeci cykl.

1 2 2 3 6

(1 2) 2 3 6

1 2 2 3 6

1 (2 2) 3 6

1 2 2 3 6

1 2 (2 3) 6

1 2 2 3 6

1 2 2 (3 6)

1 2 2 3 6

W tym momencie cykl jest zakończony i rozpoczyna się ostatni, czwarty.

1 2 2 3 6

(1 2) 2 3 6

1 2 2 3 6

1 (2 2) 3 6

1 2 2 3 6

1 2 (2 3) 6

1 2 2 3 6

1 2 2 (3 6)

1 2 2 3 6

Sortowanie bąbelkowe się kończy.

Zalety i wady – Sortowanie bąbelkowe

Zalety:

• Prostota – to bardzo prosty algorytm, co czyni go łatwym do zrozumienia i zaimplementowania, szczególnie dla celów edukacyjnych.

Wady:

• Niska wydajność dla dużych zbiorów danych – jest mało efektywny przy większych ilościach danych. Inne algorytmy, takie jak sortowanie szybkie czy przez scalanie, mają znacznie lepszą wydajność.
• Brak adaptacyjności – algorytm nie dostosowuje się do istniejącego porządku w danych wejściowych. Zawsze wykonuje tę samą liczbę porównań, niezależnie od tego, czy dane są częściowo uporządkowane czy zupełnie losowe.

Jak zrobić sortowanie bąbelkowe – implementacja algorytmu

Sortowanie bąbelkowe okazuje się prostym algorytmem, idealnym do nauki. Zrozumienie działania pseudokodu oraz schematu blokowego, zdoła Ci pomóc w opanowaniu zasad stojących za sortowaniem bąbelkowym, również w językach takich jak Python, C++ i Java.

Sortowanie bąbelkowe – Schemat blokowy i pseudokod

Opis sortowania bąbelkowego – Pseudokod

• 1 linia – Deklaracja funkcji oraz argumentów (zmiennych), które są przesyłane do niej.
• 2 linia – Pętla zewnętrzna, iteracja po indeksie i od 1 do n-1 (czyli długości tablicy-1).
• 3 linia – Pętla wewnętrzna – iteracja po indeksie j od 1 do n-1 (czyli długości tablicy-1).
• 4 linia – Warunek – porównanie aktualnego elementu z kolejnym (czy jest większy od kolejnego).
• 5 linia – Zapamiętanie wartości aktualnego elementu.
• 6 linia – Zastąpienie elementu aktualnego tab[j] kolejnym tab[j+1].
• 7 linia – Przypisanie do następnego elementu aktualnej wartości.

Sortowanie bąbelkowe – Python, C++ i Java

Sortowanie bąbelkowe zoptymalizowane – Schemat blokowy i pseudokod

Opis zoptymalizowanego sortowania bąbelkowego – Pseudokod

Aby poprawnie zaimplementować algorytm, należy użyć zagnieżdżonych pętli for. Pętla nadrzędna powinna działać n-1 razy, gdzie n oznacza liczbę elementów w sortowanym zestawie danych. Druga z pętli powinna się wykonywać n – i – 1 razy, gdzie i jest wartością iterowaną przez nadrzędną pętlę for. To właśnie fragment n – i – 1 sprawia, że posortowane już liczby (znajdujące się na końcu tablicy) nie są brane pod uwagę w trakcie kolejnych cykli. Jeżeli element o indeksie j będzie większy od elementu o indeksie j + 1 to dojdzie do zamiany wartości miejscami.

Sortowanie bąbelkowe zoptymalizowane – Python, C++ i Java

Złożoność obliczeniowa i pamięciowa – Sortowanie bąbelkowe

Złożoność obliczeniowa sortowania bąbelkowego w podstawowej wersji to O(n²).

Złożoność pamięciowa sortowania bąbelkowego to O(1).

To sortowanie o niskiej wydajności w przypadku większych zbiorów danych. Porównuje sąsiadujące ze sobą elementy póki nie przejdzie przez cały zbiór, po czym zacznie się kolejna pętla.

Sytuacją pesymistyczną w tym przypadku jest ułożenie elementów w odwrotnej kolejności (malejąco lub rosnąco, przeciwnie do działania algorytmu). Dotyczy to tylko zoptymalizowanej wresji algorytmu, bo w przypadku podstawowej, nadal wykona się tyle samo operacji, niezależnie od ułożenia elementów.

Optymalizacja sortowania bąbelkowego

Prócz wykorzystanego wcześniej sposobu, jedną z najłatwiejszych metod na optymalizację tego algorytmu jest dodanie specjalnej flagi, która poinformuje program, czy doszło do jakichkolwiek zmian w konkretnej iteracji. Jeśli nie zmieniono pozycji żadnego z elementów, to znaczy, że zbiór danych został już ułożony w odpowiedniej kolejności (rosnącej lub malejącej), a więc można zakończyć działanie algorytmu. Co prawda wydłuża to działanie pojedynczej pętli, ale może to zaoszczędzić wykonania kilku dodatkowych iteracji.

Sortowanie bąbelkowe ze względu na swoje cechy charakterystyczne jest stosowane głównie do nauki, zanim przejdzie się do bardziej skomplikowanych, a jednocześnie wydajniejszych algorytmów. Wystarczy, że raz się z nim zapoznasz, a w późniejszym czasie nie powinno być problemu z jego odtworzeniem (w ramach zadań szkolnych czy maturalnych).

Najczęściej zadawane pytania o sortowanie bąbelkowe