Sortowanie bąbelkowe

prosty, stabilny algorytm sortowania

Sortowanie bąbelkowe (ang. bubble sort) – prosta metoda sortowania o złożoności czasowej i pamięciowej

Sortowanie bąbelkowe
Ilustracja
Przykład działania algorytmu sortowania bąbelkowego
Rodzaj

sortowanie

Struktura danych

tablica, lista

Złożoność
Czasowa

Pamięciowa

Wizualizacja sortowania bąbelkowego
Wizualizacja sortowania bąbelkowego

Polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona porządek, w jakim się sortuje tablicę[1]. Sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano żadnej zmiany.

Dowód matematyczny edytuj

Algorytm opiera się na zasadzie maksimum, tj. każda liczba jest mniejsza lub równa od liczby maksymalnej. Porównując kolejno liczby, można wyznaczyć największą z nich. Następnie ciąg częściowo posortowany (mający liczbę maksymalną) można skrócić o tę liczbę i ponowić szukanie maksimum, już bez elementów odrzuconych i tak długo, aż zostanie nam jeden element. Otrzymane kolejne maksima są coraz mniejsze, przez co ciąg jest uporządkowany.

Złożoność obliczeniowa edytuj

 
Przykład działania

Algorytm wykonuje   przejść, a w każdym przejściu wykonuje   porównań (gdzie   to numer przejścia), przez co jego teoretyczna złożoność czasowa wynosi   W podstawowej wersji algorytmu nie można tego czasu skrócić, a każda permutacja powoduje, że algorytm jest wykonywany w czasie pesymistycznym.

Modyfikacje powodujące ulepszenie czasu edytuj

Algorytm można rozbudować tak, by czas optymistyczny był lepszy. Najłatwiejsze jest dodanie flagi informującej, czy w danej iteracji doszło do zmiany. Flaga jest zerowana na wejściu w przebiegu pętli, w przypadku natrafienia na zmianę jest podnoszona, a po wykonaniu przejścia sprawdzana. Jeśli nie było zmian, to sortowanie jest zakończone. Modyfikacja ta wprawdzie wydłuża czas wykonania jednego przejścia przez pętlę (gdyż trzeba wyzerować flagę, podnieść ją i sprawdzić), jednakże w wariancie optymistycznym (ciąg częściowo posortowany) może zaoszczędzić iteracji, przez co algorytm będzie działać szybciej.

Przykład działania edytuj

Ciąg wejściowy   Każdy wiersz symbolizuje wypchnięcie kolejnego największego elementu na koniec („wypłynięcie największego bąbelka”). Niebieskim kolorem oznaczono końcówkę ciągu już posortowanego.

 
 
 
 

Sortowanie bąbelkowe w C++ edytuj

Oto sortowanie w C++ wersji podstawowej algorytmu dla tablicy o rozmiarze n (elementy tablicy są numerowane od 0 do n-1):

#include <iostream>

using namespace std;

void Bubblesort(int tab[], int n){
    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]);
            }
        }
    }

    for(int i = 0; i < n; i++){
        cout << tab[i] << " ";
    }
    cout << "\n";
}

int main(){

    int tab[] = {4, 2, 1, 7, 10};
    int n = 5;

    Bubblesort(tab, n);

    return 0;
}

Implementacja edytuj

Linki zewnętrzne edytuj

Przypisy edytuj

  1. Bubble Sort - Data Structure and Algorithm Tutorials [online], GeeksforGeeks, 2 lutego 2014 [dostęp 2023-07-12] (ang.).