- 18 kwietnia 2024
- Posted by: Daria
- Category: Baza wiedzy
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
1 2 3 4 5 6 7 8 | funkcja sortowanie_babelkowe (tab, n) dla i = 1, 2, … n-1 wykonuj dla j = 1, 2, … n-1 wykonuj jeżeli tab [j] > tab [j+1] zmienna ← tab [j] tab [j] ← tab [j+1] tab [j+1] ← zmienna zwróć tab |
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 – Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | # Deklaracja listy 'tab' tab = [5, 3, 8, 2, 1, 7] # Kod sortowania bąbelkowego podstawowego n = len(tab) for i in range(n - 1): for j in range(n - 1): if tab[j] > tab[j + 1]: zmienna = tab[j] tab[j] = tab[j + 1] tab[j + 1] = zmienna # Wyświetlanie posortowanej listy for element in tab: print(element, end=" ") |
Sortowanie bąbelkowe – C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #include <iostream> using namespace std; int main() { // Deklaracja tablicy 'tab' int tab[] = {5, 3, 8, 2, 1, 7}; int n = sizeof(tab) / sizeof(tab[0]); // pozwoli to automatycznie odczytać ilosc elementow w tablicy // Kod sortowania bąbelkowego podstawowego for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1; j++) { if (tab[j] > tab[j+1]) { int zmienna = tab[j]; tab[j] = tab[j+1]; tab[j+1] = zmienna; } } } // Wyświetlanie posortowanej tablicy for (int i = 0; i < n; i++) { cout << tab[i] << " "; } return 0; } |
Sortowanie bąbelkowe – Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | public class Main { public static void main(String[] args) { // Deklaracja tablicy 'tab' int[] tab = {5, 3, 8, 2, 1, 7}; // Kod sortowania bąbelkowego podstawowego for (int i = 0; i < tab.length - 1; i++) { for (int j = 0; j < tab.length - 1; j++) { if (tab[j] > tab[j+1]) { int zmienna = tab[j]; tab[j] = tab[j+1]; tab[j+1] = zmienna; } } } // Wyswietlanie posortowanej tablicy for (int element : tab) { System.out.print(element + " "); } } } |
Sortowanie bąbelkowe zoptymalizowane – Schemat blokowy i pseudokod
1 2 3 4 5 6 7 8 | funkcja sortowanie_babelkowe_zoptymalizowane (tab, n) dla i = 1, 2, … n - 1 wykonuj dla j = 1, 2, … n - i - 1 wykonuj jeżeli tab [j] > tab [j+1] zmienna ← tab [j] tab [j] ← tab [j+1] tab [j+1] ← zmienna zwróć tab |
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
Sortowanie bąbelkowe zoptymalizowane – Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | # Deklaracja listy 'tab' tab = [5, 3, 8, 2, 1, 7] # Kod sortowania bąbelkowego zoptymalizowanego n = len(tab) for i in range(n - 1): for j in range(n - i - 1): if tab[j] > tab[j + 1]: zmienna = tab[j] tab[j] = tab[j + 1] tab[j + 1] = zmienna # Wyświetlanie posortowanej listy for element in tab: print(element, end=" ") |
Sortowanie bąbelkowe zoptymalizowane – C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #include <iostream> using namespace std; int main() { // Deklaracja tablicy 'tab' int tab[] = {5, 3, 8, 2, 1, 7}; int n = sizeof(tab) / sizeof(tab[0]); // pozwoli to automatycznie odczytać ilość elementów w tablicy // Kod sortowania bąbelkowego zoptymalizowanego for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (tab[j] > tab[j+1]) { int zmienna = tab[j]; tab[j] = tab[j+1]; tab[j+1] = zmienna; } } } // Wyświetlanie posortowanej tablicy for (int i = 0; i < n; i++) { cout << tab[i] << " "; } return 0; } |
Sortowanie bąbelkowe zoptymalizowane – Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | public class Main { public static void main(String[] args) { // Deklaracja tablicy 'tab' int[] tab = {5, 3, 8, 2, 1, 7}; // Kod sortowania bąbelkowego zoptymalizowanego for (int i = 0; i < tab.length - 1; i++) { for (int j = 0; j < tab.length - i - 1; j++) { if (tab[j] > tab[j+1]) { int zmienna = tab[j]; tab[j] = tab[j+1]; tab[j+1] = zmienna; } } } // Wyswietlanie posortowanej tablicy for (int element : tab) { System.out.print(element + " "); } } } |
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
Czy sortowanie bąbelkowe jest stabilne?
Jak najbardziej jest stabilne, a co za tym idzie nie zmienia kolejności identycznych elementów w sortowanym zbiorze danych.
Jakie są alternatywy dla sortowania bąbelkowego?
Można tu wymienić takie sortowania jak szybkie, przez scalanie, kopcowanie lub introspektywne.
Czy algorytm sortowania bąbelkowego jest najszybszy?
Nie, algorytm sortowania bąbelkowego nie jest najszybszym algorytmem sortowania, zwłaszcza dla większych zbiorów danych. Efektywniejsze jest sortowanie szybkie czy przez scalanie.