Metoda bulelor (bubble-sort)

Algoritmul const n parcurgerea tabloului A de mai multe ori, pn cnd devine ordonat. La fiecare pas se compar dou elemente alturate. Dac ai > ai + 1, (i = 1, 2, ..., n 1), atunci cele

dou valori se interschimb ntre ele. Controlul aciunii repetitive este dat de variabila boolean

ok, care la fiecare reluare a algoritmului primete valoarea iniial adevrat, care se schimb n fals dac s-a efectuat o interschimbare de dou elemente alturate. n momentul n care

tabloul A s-a parcurs fr s se mai efectueze nici o schimbare, ok rmne cu valoarea iniial adevrat i algoritmul se termin, deoarece tabloul este ordonat.

Interschimbarea a dou elemente se realizeaz prin intermediul variabilei auxiliare aux care are acelai tip ca i elementele tabloului.

Subalgoritm Metoda_bulelor (A) 1: repeta

2: ok = adevrat 3: pentru i=1,n-1 execut 4: dac a[i] > a[i+1] atunci 5: ok = fals 6: aux = a[i] 7: a[i] = a[i+1] 8: a[i+1] = aux 9: pana cand ok

Considerm tabloul A cu 5 elemente numere reale: 0.0, 1.1, 1.0, 1.2 i 0.08. Prima parcurgere a

tabloului (ok este iniializat cu adevrat):

a1 = 0.0 a2 = 1.1 a3 = 1.0 a4 = 1.2 a5 = 0.08 ok

0.0 1.0 1.1 1.2 0.08 fals

0.0 1.0 1.1 0.08 1.2 fals

Valorile 0.0 < 1.1, rmn neschimbate, 1.1 > 1.0, le interschimbm. Deoarece 1.1 < 1.2, avansm i constatm c 1.2 > 0.0.8, deci din nou avem interschimbare. n consecin, la ieire

din structura pentru ok este fals. Observm c 1.2 a ajuns pe locul lui definitiv. Urmeaz a doua parcurgere a tabloului (ok primete din nou valoarea adevrat).

a1 = 0.0 a2 = 1.0 a3 = 1.1 a4 = 0.08 a5 = 1.2 ok

0.0 1.0 0.08 1.1 1.2 fals

Am avut interschimbare i de data aceasta, deci ieim cu ok = fals. La acest pas 1.1 a ajuns pe locul su definitiv. A treia parcurgere a tabloului ncepe cu reiniializarea lui ok cu valoarea adevrat.

a1 = 0.0 a2 = 1.0 a3 = 0.08 a4 = 1.1 a5 = 1.2 ok

0.0 0.08 1.0 1.1 1.2 fals

Am interschimbat 0.08 cu 1.0, cel din urm astfel a ajuns pe locul su n irul ordonat. A patra parcurgere a tabloului se finalizeaz cu valoarea ok = adevrat, deoarece nu am efectuat nici o interschimbare, ceea ce nseamn c procesul de ordonare s -a ncheiat.

a1 = 0.0 a2 = 0.08 a3 = 1.0 a4 = 1.1 a5 = 1.2 ok

0.0 0.08 1.0 1.1 1.2 adevrat

Observaia cu privire la faptul c la fiecare parcurgere a ajuns cel puin un element pe locul su

definitiv n irul ordonat poate fi fructificat, deoarece constatm c astfel, la urmtorul pas nu mai sunt necesare verificrile n care intervine acest element i cele care se afl dup el n ir.

Rezult c la fiecare parcurgere am putea micora cu 1 numrul elementelor verificate. Astfel, ajungem la urmtorul subalgoritm mbuntit ca performan:

Subalgoritm Metoda_bulelor (A)

1: k=n {k va fi limita superioara pana unde se interschimba elemente} 2: repeta

3: ok = adevrat 4: pentru i=1,k-1 execut

5: dac a[i] > a[i+1] atunci 6: ok = fals

7: aux = a[i] 8: a[i] = a[i+1]

9: a[i+1] = aux 10: j=i 11: k=j; {ultimul indice pentru care s-a facut interchimbare} 12: pana cand ok

Metoda bulelor nu este cea mai performant modalitate de a ordona un ir cu multe elemente, dar n cazul irurilor aproape ordonate, cu optimizrile de mai sus, poate deveni mai eficient dect alte metode. Pentru a analiza timpul de execuie al metodei bulelor trebuie s lum n considerare 3 mrimi:

1. numrul de treceri (parcurgeri)

2. numrul de interschimbri 3. numrul de comparaii Dac presupunem c valorile de intrare reprezint o permutare a mulimii {1, 2, ..., n} putem uor descrie efectul fiecrei treceri astfel: dac un element ai nu are nici un precedent mai mare el va rmne pe loc, iar daca are cel puin unul mai mare atunci el se va muta cu o poziie mai n fa. Reamintesc c elementul maxim de la fiecare parcurgere va ajunge pe poziia final. Astfel, eficiena metodei bulelor depinde de numrul de inversiuni din permutarea iniial (fa de permutarea final, cea identic). Voi defini n continuare inversiunea i proprietile

inversiunilor. Definiie: Fie a1, a2, ... an o permutare a mulimii {1, 2, ..., n}. Dac iaj, atunci perechea

(ai, aj) se numete inversiunii a permutrii. De exemplu, n permutarea 3,1,4,2 se gsesc 3 inversiuni: (3,1), (3,2) i (4,2).

Observaie: Singura permutare fr inversiuni este cea ordonat (identic) 1,2,...,n. Cazul cel mai favorabil este acela n care datele iniiale sunt ordonate cresctor, caz n care se

face o singur parcurgerea a datelor.

Cazul cel mai nefavorabil este cel n care datele sunt sortate descresctor, caz n care se vor face n-1 parcurgeri. La prima parcurgere se vor face n-1 interschimbri, la a doua n-2 i aa mai

departe. Aadar numrul de comparaii i cel de interschimbri va fi n(n-1)/2. Exemplu n acest caz:

Numrul parcurgerii

a1 a2 a3 a4 Numrul de interschimbri

iniial 4 3 2 1

1 3 2 1 4 3

2 2 1 3 4 2

3 1 2 3 4 1

Total interschimbri 6

Astfel, vom spune c metoda bulelor are un timp de execuie n cazul cel mai defavorabil de

(n2).