Algorytm sortowania bąbelkowego jest jednym z najstarszych algorytmów sortujących. Można go potraktować jako ulepszenie opisanego w poprzednim rozdziale algorytmu sortowania głupiego. Zasada działania opiera się na cyklicznym porównywaniu par sąsiadujących elementów i zamianie ich kolejności w przypadku niespełnienia kryterium porządkowego zbioru. Operację tę wykonujemy dotąd, aż cały zbiór zostanie posortowany.

Algorytm sortowania bÄ…belkowego przy porzÄ…dkowaniu zbioru nieposortowanego ma klasÄ™ czasowej zÅ‚ożonoÅ›ci obliczeniowej równÄ… O(n²). Sortowanie odbywa siÄ™ w miejscu.

Jako przykład działania algorytmu sortowania bąbelkowego posortujemy przy jego pomocy 5-cio elementowy zbiór liczb {5 4 3 2 1}, który wstępnie jest posortowany w kierunku odwrotnym, co możemy uznać za przypadek najbardziej niekorzystny, ponieważ wymaga przestawienia wszystkich elementów.

Obieg	Zbiór	Opis operacji
1	 5 4 3 2 1Â	Rozpoczynamy od pierwszej pary, która wymaga wymiany elementów
		 4 5 3 2 1Â	Druga para też wymaga zamiany elementów
		 4 3 5 2 1Â	Wymagana wymiana elementów
		 4 3 2 5 1Â	Ostatnia para również wymaga wymiany elementów
		 4 3 2 1 5Â	Stan po pierwszym obiegu. Zwróć uwagÄ™, iż najstarszy element (5) znalazÅ‚ siÄ™ na koÅ„cu zbioru, a najmÅ‚odszy (1) przesunÄ…Å‚ siÄ™ o jednÄ… pozycjÄ™ w lewo.
	2	 4 3 2 1 5Â	Para wymaga wymiany
		 3 4 2 1 5Â	Para wymaga wymiany
		 3 2 4 1 5Â	Para wymaga wymiany
		 3 2 1 4 5Â	Elementy sÄ… w dobrej kolejnoÅ›ci, zamiana nie jest konieczna.
		 3 2 1 4 5Â	Stan po drugim obiegu. Zwróć uwagÄ™, iż najmniejszy element (1) znów przesunÄ…Å‚ siÄ™ o jednÄ… pozycjÄ™ w lewo. Z obserwacji tych można wywnioskować, iż po każdym obiegu najmniejszy element wÄ™druje o jednÄ… pozycjÄ™ ku poczÄ…tkowi zbioru. Najstarszy element zajmuje natomiast swe miejsce koÅ„cowe.
	3	 3 2 1 4 5Â	Para wymaga wymiany
		 2 3 1 4 5Â	Para wymaga wymiany
		 2 1 3 4 5Â	Dobra kolejność
		 2 1 3 4 5Â	Dobra kolejność
		 2 1 3 4 5Â	Stan po trzecim obiegu. Wnioski te same.
	4	 2 1 3 4 5Â	Para wymaga wymiany
		 1 2 3 4 5Â	Dobra kolejność
		 1 2 3 4 5Â	Dobra kolejność
		 1 2 3 4 5Â	Dobra kolejność
		 1 2 3 4 5Â	Zbiór jest posortowany. Koniec

Posortowanie naszego zbioru wymaga 4 obiegów. Jest to oczywiste: w przypadku najbardziej niekorzystnym najmniejszy element znajduje się na samym końcu zbioru wejściowego. Każdy obieg przesuwa go o jedną pozycję w kierunku początku zbioru. Takich przesunięć należy wykonać n - 1 (n - ilość elementów w zbiorze).

Algorytm sortowania bÄ…belkowego, w przeciwieÅ„stwie do algorytmu sortowania gÅ‚upiego, nie przerywa porównywania par elementów po napotkaniu pary nie speÅ‚niajÄ…cej zaÅ‚ożonego porzÄ…dku. Po zamianie kolejnoÅ›ci elementów sprawdzana jest kolejna para elementów sortowanego zbioru. DziÄ™ki temu podejÅ›ciu roÅ›nie efektywność algorytmu oraz zmienia siÄ™ klasa czasowej zÅ‚ożonoÅ›ci obliczeniowej z O(n³) na O(n²).

// Sortowanie BÄ…belkowe - Wersja nr 1

//-------------------------------------------------

// (C)2005 mgr Jerzy Wałaszek

// I Liceum Ogólnokształcące

// im. K. Brodzińskiego

// w Tarnowie

//-------------------------------------------------

#include <cmath>

#include <iostream>

#include <iomanip>

using namespace std;

const int N = 20; // Liczebność zbioru.

// Program główny

//---------------

main()

{

int d[N],i,j;

cout << " Sortowanie babelkowe\n"

" WERSJA NR 1\n"

"----------------------\n"

"(C)2005 Jerzy Walaszek\n\n"

"Przed sortowaniem:\n\n";

// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi

// a następnie wyświetlamy jej zawartość

srand((unsigned)time(NULL));

for(i = 0; i < N; i++) d[i] = rand() % 100;

for(i = 0; i < N; i++) cout << setw(4) << d[i];

cout << endl;

// Sortujemy

for(j = 0; j < N - 1; j++)

for(i = 0; i < N - 1; i++)

if(d[i] > d[i + 1]) swap(d[i], d[i + 1]);

// Wyświetlamy wynik sortowania

cout << "Po sortowaniu:\n\n";

for(i = 0; i < N; i++) cout << setw(4) << d[i];

cout << endl;

system("PAUSE");

}

---