Sortowanie bąbelkowe

Sortowanie bąbelkowe

Sortowanie bąbelkowe (ang. bubble sort) to prosta metoda sortowania o złożoności czasowej $O(n^2)$ i pamięciowej $O(1)$. Algorytm polega na porównywaniu dwóch sąsiednich elementów i ich zamianie, jeśli są w złej kolejności. Proces ten kończy się, gdy w trakcie przejścia nie dokonano żadnej zmiany.

Dowód matematyczny

Algorytm opiera się na zasadzie maksymalności, gdzie każda liczba jest mniejsza lub równa liczbie maksymalnej. Porównując liczby, można wyznaczyć największą z nich, a następnie powtarzać proces z pozostałymi elementami, aż pozostanie tylko jeden.

Złożoność obliczeniowa

Algorytm wykonuje $n-1$ przejść, a w każdym z nich wykonuje $n-k$ porównań, co prowadzi do teoretycznej złożoności czasowej $O(n^2)$. W podstawowej wersji algorytmu nie można skrócić tego czasu, a każda permutacja powoduje, że algorytm działa w czasie pesymistycznym.

Modyfikacje poprawiające czas

• Dodanie flagi informującej o zmianach w iteracji, co pozwala na wcześniejsze zakończenie sortowania, gdy nie było wymiany.

Ta modyfikacja zwiększa czas jednego przejścia, ale może przyspieszyć cały proces w przypadku, gdy tablica jest częściowo posortowana.

Przykład działania

Dla ciągu wejściowego $[4,\; 2,\; 5,\; 1,\; 7]$ proces sortowania ilustruje wypychanie największego elementu na koniec ciągu. Niebieskim kolorem zaznaczono końcówkę już posortowanego ciągu:

Sortowanie bąbelkowe w C++

Poniżej znajduje się podstawowa wersja algorytmu w C++ dla tablicy o rozmiarze n:

#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;
}

Linki zewnętrzne

• Algorytm przedstawiony z wykorzystaniem tańca węgierskiego