Przejdź do zawartości

Sortowanie bąbelkowe

Z Wikipedii, wolnej encyklopedii
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

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

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 | edytuj kod]

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 | edytuj kod]
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 | edytuj kod]

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 | edytuj kod]

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.

Implementacja

[edytuj | edytuj kod]

Poniżej zaimplementowano algorytm sortowania bąbelkowego w C++ oraz w Pythonie. W przykładzie w C++ zmienna n przekazuje rozmiar tablicy, a w obu przykładach elementy tablicy numerowane są od 0 do n - 1.

#include <iostream>
#include <algorithm>

void bubble_sort(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]) {
                std::swap(tab[j], tab[j + 1]);
            }
        }
    }
}

int main() {
    int tab[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(tab) / sizeof(tab[0]);

    bubble_sort(tab, n);

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

    return 0;
}

Python

[edytuj | edytuj kod]
def bubble_sort(lista):
    n = len(lista)
    for i in range(n):
        for j in range(n - i - 1):
            if lista[j] > lista[j + 1]: 
                lista[j], lista[j + 1] = lista[j + 1], lista[j]

lista = [64, 34, 25, 12, 22, 11, 90]

bubble_sort(lista)

for i in lista:
    print(i, end = " ")
print()

Linki zewnętrzne

[edytuj | edytuj kod]

Przypisy

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