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