SORTAREA PRIN INTERSCHIMBARE (BUBBLE SORT)
În cadrul acestei metode de sortare vom parcrge urmatorii pași:
1. Se compară fiecare pereche de elemente adiacente de la începutul tabloului unidimensional (vector) şi dacă elementele nu sunt în ordinea pe care o dorim, le interschimbăm.
2. Dacă s-a făcut cel puţin o interschimbare , repetăm pasul 1. Algoritmul se încheie când la o nouă parcurgere nu se mai face nici o interschimbare ( adică vectorul este sortat).
Exemplu
Să sortăm şirul {8, 1, 11, -3, 15} folosind metoda bulelor( Folosim următoarea convenție scriem cu rosu elemente ce se sortează la un moment dat si cu verde elementele ce sunt sortate corespunzător )
8, 1, 11, -3, 15; nesortat
8, 1, 11, -3, 15; 8>1 interschimbăm
1, 8, 11, -3, 15; 8<11 nu se face interschimbare
1, 8, 11, -3, 15; 11>-3 interschimbăm
1, 8, -3 11, 15; 11<15 nu se face interschimbare
1, 8, -3 11, 15; 1<8 nu se face interschimbare
1, 8, -3 11, 15; 8>-3 interschimbăm
1, -3, 8, 11, 15; 8<11 nu se face interschimbare
1, -3, 8, 11, 15; 1>-3 interschimbăm
-3, 1, 8, 11, 15; 1<8 nu se face interschimbare
-3, 1, 8, 11, 15; -3<1 nu se face interschimbare
-3, 1, 8, 11, 15; vector sortat
Implementare în C++
void bubbleSort(int v[], int n)
{
int ok = 1;
int j = 0;
int aux;
while (ok)
{
ok = 0;
j++;
for (int i = 0; i < n - j; i++)
if (v[i] > v[i + 1]) {
aux = v[i]; v[i] = v[i + 1];
v[i + 1] = aux;
ok =1;}
}}
Algoritm descris în pseudocod
ok←true
j←0
cât timp ok execută
ok←false
j←j+1
pentru i ←1,n-j execută
dacă v[i]>v[i+1] atunci
v[i] ↔ v[j]
sfdacă
sfpentru
sfcât timp