Sortowanie bąbelkowe
![]() Przykład działania algorytmu sortowania bąbelkowego | |
Rodzaj | |
---|---|
Struktura danych | |
Złożoność | |
Czasowa |
|
Pamięciowa |
|

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]
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
.
C++
[edytuj | edytuj kod]#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]- ↑ Bubble Sort - Data Structure and Algorithm Tutorials [online], GeeksforGeeks, 2 lutego 2014 [dostęp 2023-07-12] (ang.).