SORTAREA PRIN METODA BULELOR

MULTIME NESORTATA MULTIME SORTATA PRIN BUBBLESORT

Ideea de baza a sortarii prin metoda bulelor este in a parcurge tabloul de la stanga spre dreapta, fiind comparate elementele alaturate a[ i ] si a[i+1]. Daca vor fi gasite 2 elemente neordonate valorile lor vor fi interschimbate.

Parcurgerea tabloului de la stinga spre dreapta se va repeta atat timp cat vor fi intalnite elemente neordonate.

Sortarea prin metoda bulelor se considera drept una din cele mai putin eficiente metode de sortare dar cu un algoritm mai putin complicat.

PRINCIPIUL METODEI

Vectorul prelucrat Numarulparcurger

ii10 5 6 12 3 7 12

15 10 6 12 3 7 125 6 10 12 3 7 125 6 10 12 3 7 125 6 10 3 12 7 125 6 10 3 7 12 125 6 10 3 7 12 12

25 6 10 3 7 12 125 6 10 3 7 12 125 6 3 10 7 12 125 6 3 7 10 12 12

35 6 3 7 10 12 125 3 6 7 10 12 125 3 6 7 10 12 12 43 5 6 7 10 12 12

EXEMPLU

•Fiecare pereche analizata este evidentiata printr-un chenar dublu, colorata gri in cazul in care elementele trebuie interschimbate.

• Limita fiecarei etape de verificare este marcata prin linie dubla mai groasa.

ALGORITM

nr_parc:=0; {variabila contor numara la a cata parcurgere a vectorului suntem; parcurgerea vectorului se repeta pana cand la o parcurgere nu se mai pot face interschimbari}

repeat inv:=false;nr_parc:=nr_parc+1;for i:=1 to n-nr_parc do

  if a[i]>a[i+1] then     begin           aux:=a[i];           a[i]:=a[i+1];             a[i+1]:=aux;

inv:=true       end;until inv=false;

ANIMATIE BUBBLESORT

10 5 6 12 3neterminata….!!

s.a.m.d.

Dupa prima parcurgere a vectorului, elementul maxim e asezat pe pozitia sa finala!!!

Elementele alaturate se compara si daca nu sunt in ordinea dorita, se intershimba.

COMPLEXITATEA ALGORITMULUI

Sortarea prin meteoda bulelor este o metoda de sortare simpla, eficienta pentru un numar mic de elemente (mai putin de 15), dar nu pentru tablouri mari.

Bubblesort este extrem de eficienta în ceea ce priveşte utilizarea memoriei, datorită faptului că toate operaţiunile de triere sunt efectuate pe multimea initiala de date.

Timpul de executie depinde de ordinea initiala a elementelor. Daca tabloul este deja sortat e nevoie de un singur pas, adica N-1 comparari. In cazul cel mai nefavorabil sunt necesare N ×(N-1)/2 comparari si N × (N-1)/2 interschimbari. Performanta algoritmului in caz general este mai greu de analizat dar este asemanator cazului nefavorabil.

APLICATIE

In prima ora de Educatie fizica a fiecarui an scolar, profesorul trebuie sa-si aseze elevii fiecarei clase in ordine crescatoare dupa inaltime. Cum ii sugerati sa procedeze?

IMPLEMENTARE

var a:array[1..100] of integer; x,n i,k:integer; inv:boolean;begin write(‘dati numarul de elevi din clasa’); readln(n); for i:=1 to n do begin write(‘inaltimea elevului ’, i); readln(a[i]); end; nr_parc:=0; repeat

inv:=false;nr_parc:=nr_parc+1;for i:=1 to n-nr_parc do

  if a[i]>a[i+1] then     begin           aux:=a[i];           a[i]:=a[i+1];             a[i+1]:=aux;

inv:=true       end; until inv=false; write(‘elevii aranjati crescator dupa inaltime’); for i:=1 to n do write(a[i], ‘ ‘);end.

BUBBLE.EXE

BIBLIOGRAFIE

http://dranaxum.files.wordpress.com/2007/11/studiu-asupra-timpilor-de-sortare.pdf

http://buffered.io/2008/08/14/sorting-algorithms-the-bubble-sort/ http://hosok2.com/project/dataExpansion_1/

Bubble_sort_animation.gif