Sortowanie bąbelkowe (bubble sort)

Sortowanie bąbelkowe jest jednym z najprostszych algorytmów, który umożliwia posortowanie danych malejąco bądź rosnąco. Nazwa algorytmu pochodzi od jego implementacji. 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 (przy sortowaniu rosnąco)/ mniejsza (przy sortowaniu malejąco) zostaje przesunięta w prawą stronę. Algorytm kończy się, gdy wszystkie wartości zostaną ułożone w zadanej kolejności.

Należy pamiętać, że ten algorytm nie jest zbyt dobrym wyborem, jeżeli naszym zadaniem jest posortowanie dużej ilości danych. W takiej sytuacji wykonywać się on będzie dużo dłużej, w przeciwieństwie do innych, znanych metod sortowania np. sortowania przez wstawianie.

Przykład algorytmu sortowania bąbelkowego

Przy pomocy algorytmu sortowania bąbelkowego posortujmy poniższą tablicę danych w kolejności rosnącej. Począwszy od lewej strony należy porównywać ze sobą po dwie kolejne wartości.

Poniższa animacja prezentuje sposób działania algorytmu. Zwróć uwagę, że gdy wykonamy pierwszy cykl sortowania to na końcu będzie się znajdować najwyższa wartość. Wiedząc o tym, możemy ograniczyć ilość wykonywanych porównań w kolejnych cyklach. Wartości posortowane będą znajdowały się po prawej stronie, a te nieposortowane po lewej.

Implementacja algorytmu sortowania bąbelkowego

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 – 1 – i razy, gdzie i jest wartością iterowaną przez nadrzędną pętlę for. Jeżeli element o indeksie j będzie większy od elementu o indeksie j + 1 to dojdzie do zamiany wartości miejscami.

Implementacja algorytmu sortowania bąbelkowego C++

for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
        if (tab[j] > tab[j + 1])
            swap(tab[j], tab[j + 1]);
    }
}

Implementacja algorytmu sortowania bąbelkowego Python

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