Algorytm sortowania „bąbelkowego” jest jednym z najprostszych algorytmów służących do sortowania liczb, o złożoności czasowej O(N2) i pamięciowej O(1).
Jego nazwa wzięła się od „pęcherzyków powietrza”, które ulatywały w górę tuby wypełnionej wodą. Jeżeli tablicę danych potraktujemy jak pojemnik z wodą, a zawarte w niej dane jako pęcherzyki powietrza, to najszybciej do góry będą lecieć najlżejsze, czyli liczby o najmniejszej wartości.
Algorytm ten opiera się na zasadzie „maximum”. To znaczy, że każda liczba jest mniejsza lub równa w stosunku do liczby maksymalnej. Kiedy będziemy porównywać kolejno liczby, to możemy wyznaczyć największą z nich. Następnie pozostałe dane możemy skrócić o znalezioną wcześniej liczbę i po raz kolejny szukać największej liczby. Ten element będziemy powtarzać do momentu kiedy zostanie nam tylko jedna liczba. Dzięki czemu ciąg liczb będzie uporządkowany.
Kod będzie wykonywał n-1 przejść, a w każdym przejściu n-1 porównań. Więc jego teoretyczna złożoność czasowa będzie wynosić O(n2).
Przykład działania
Załóżmy, że mamy ciąg wejściowy [4,2,5,1,7], a każdy kolejny wiersz znajdujący się na poniższej ilustracji symbolizuje wypchnięcie największego elementu na koniec:

Przykładowy program wykorzystujący algorytm sortowania bąbelkowego (napisany w języku Pascal):
program sortowanieBabelkowe;
USES crt;
VAR
liczby:array[1..6] of integer;
i,j,tmp:integer;
BEGIN
clrscr;
{wypełniamy tablice liczbami}
writeln('Podaj 6 liczb, które chcesz posortować:');
for i:= 1 to 6 do
readln(liczby[i]); {zapisujemy liczby}
{sortowanie}
for i:=1 to 5 do
for j:=1 to 5 do
if liczby[j] > liczby[j+1] then
begin
tmp := liczby[j];
liczby[j] := liczby[j+1];
liczby[j+1] := tmp;
end;
{wyświetlamy posortowane liczby}
writeln('Posortowane liczby:');
for i:=1 to 6 do
writeln(liczby[i]);
repeat until keypressed;
END.Przebieg sortowania krok po kroku
Prześledźmy jeden pełny przebieg na tablicy [5, 1, 4, 2]. Porównujemy sąsiadów i zamieniamy, gdy lewy jest większy:
| Porównanie | Tablica po kroku | Zamiana? |
|---|---|---|
| 5 i 1 | [1, 5, 4, 2] | tak |
| 5 i 4 | [1, 4, 5, 2] | tak |
| 5 i 2 | [1, 4, 2, 5] | tak |
Po pierwszym przebiegu największa liczba „wypłynęła” na koniec, dokładnie jak bąbelek z nazwy algorytmu. Kolejne przebiegi robią to samo dla coraz krótszego fragmentu, aż tablica będzie posortowana: po drugim przebiegu mamy [1, 2, 4, 5] i koniec.
Implementacja w C++ z optymalizacją
#include <iostream>
using namespace std;
int main() {
int tab[] = {5, 1, 4, 2, 8, 3};
int n = 6;
for (int i = 0; i < n - 1; i++) {
bool zamiana = false; // optymalizacja: flaga
for (int j = 0; j < n - 1 - i; j++) { // koniec juz posortowany
if (tab[j] > tab[j + 1]) {
swap(tab[j], tab[j + 1]);
zamiana = true;
}
}
if (!zamiana) break; // caly przebieg bez zamian = posortowane
}
for (int i = 0; i < n; i++) cout << tab[i] << " ";
return 0;
}Dwie rzeczy poprawiają tu podstawową wersję. Wewnętrzna pętla kończy się na n - 1 - i, bo końcówka tablicy jest już posortowana po wcześniejszych przebiegach. Flaga zamiana pozwala wyjść wcześniej: przebieg bez ani jednej zamiany oznacza, że dane są już uporządkowane. Dzięki fladze posortowana tablica kosztuje tylko jeden przebieg, czyli O(n) w najlepszym przypadku.
To samo w Pythonie
def sortowanie_babelkowe(tab):
n = len(tab)
for i in range(n - 1):
zamiana = False
for j in range(n - 1 - i):
if tab[j] > tab[j + 1]:
tab[j], tab[j + 1] = tab[j + 1], tab[j]
zamiana = True
if not zamiana:
break
return tab
print(sortowanie_babelkowe([5, 1, 4, 2, 8, 3])) # [1, 2, 3, 4, 5, 8]Skąd bierze się złożoność O(n²) i czy to dużo?
Dwie zagnieżdżone pętle po tablicy dają w najgorszym przypadku około n·n/2 porównań, a stałe w notacji pomijamy, stąd O(n²). Co to znaczy w praktyce, opisałem szerzej we wpisie o złożoności obliczeniowej: przy tysiącu elementów to już milion operacji, podczas gdy dobre sortowania (przez scalanie, quicksort) potrzebują około dziesięciu tysięcy. Dlatego sortowanie bąbelkowe ma dziś wartość głównie dydaktyczną: jest świetne do nauki myślenia algorytmicznego, ale w realnym kodzie sortujemy funkcją biblioteczną (std::sort, sorted()).
Wersje w Javie i C#
Java:
import java.util.Arrays;
public class Main {
public static void sortowanieBabelkowe(int[] tab) {
for (int i = 0; i < tab.length - 1; i++) {
boolean zamiana = false;
for (int j = 0; j < tab.length - 1 - i; j++) {
if (tab[j] > tab[j + 1]) {
int tmp = tab[j];
tab[j] = tab[j + 1];
tab[j + 1] = tmp;
zamiana = true;
}
}
if (!zamiana) break; // brak zamian = posortowane
}
}
public static void main(String[] args) {
int[] liczby = {5, 1, 4, 2, 8, 3};
sortowanieBabelkowe(liczby);
System.out.println(Arrays.toString(liczby)); // [1, 2, 3, 4, 5, 8]
}
}C#:
using System;
class Program
{
static void SortowanieBabelkowe(int[] tab)
{
for (int i = 0; i < tab.Length - 1; i++)
{
bool zamiana = false;
for (int j = 0; j < tab.Length - 1 - i; j++)
{
if (tab[j] > tab[j + 1])
{
(tab[j], tab[j + 1]) = (tab[j + 1], tab[j]);
zamiana = true;
}
}
if (!zamiana) break;
}
}
static void Main()
{
int[] liczby = {5, 1, 4, 2, 8, 3};
SortowanieBabelkowe(liczby);
Console.WriteLine(string.Join(" ", liczby)); // 1 2 3 4 5 8
}
}


Lepiej znać tak sobie wydajne sortowanie, aniżeli żadne :)