METODE DE SORTARE

Sortarea rapidă QuickSort 

• Informaţii generale
• Aplicaţii
• Vizualizare animatie algoritm                                                      Google

 

Informaţii generale: 

     Quick Sort este unul dintre cei mai rapizi şi mai utilizaţi algoritmi de sortare până în acest moment, bazându-se pe tehnica  "Divide et Impera".

    Sortarea rapidă se realizează într-o funcţie care, aplicată unui şir de numere, poziţionează un element din şir, pivot, pe poziţia finală, pe care se va afla acesta în şirul sortat, şi deplasează elementele din şir mai mici decât acesta în faţa sa, iar pe cele mai mari după el. Procedeul se reia pentru fiecare din cele două subşiruri care au rămas neordonate.

      

Algoritmul se poate descrie în următoarele etape:

Etapa Divide:  Vectorul x, format din elementele aflate între indicii i şi j, notat în continuare x[i..j], este împărţit în doi subvectori x[i ..m] şi x[m+1 ..j], fiecaresubvector având cel puţin un element şi fiecare element din primul subvector fiind mai mic sau egal decât oricare element din cel de-al doilea subvector.

Etapa Impera: Cele două părţi sunt sortate apelând recursiv, până când se ajunge la subvectori formaţi dintr-un singur element.

Combinarea: Având în vedere că fiecare subvector este sortat şi că cel mai mare element din subvectorul stâng este mai mic decât cel mai mic element dinsubvectorul drept, atunci întregul vector va fi sortat.

 

      Cea mai importantă etapă este cea de partiţionare. Există mai multe moduri în care se poate împărţi vectorul, dar următorul algoritm, inventat de R. Sedgevvick, pare a fi cel mai bun: se porneşte de la ambele capete, folosind doi indicatori, i pentru partea stângă şi j pentru partea dreaptă, căutându-se elementele care ar trebui să fie în cealaltă parte; în momentul în care se găsesc două elemente care nu sunt în ordinea dorită şi dacă iinterschimbă şi se continuă algoritmul; altfel, algoritmul întoarce valoarea lui j; element de referinţă se consideră ca fiind primul element din vector.

 

Prezentarea algoritmului:

      Următorul algoritm partiţionează vectorul x[i ..j] în doi subvectori, x[i ..m] şi x[m+1 ..j], astfel încât toate elementele din primul subvector să fie mai mici sau egale decât oricare element din cel de-al doilea subvector, la final returnându-se valoarea lui m:

 P1. Se iniţializează pivotul v cu x[i], i cu indicele valorii cea mai din stânga a vectorului de sortat, iar j cu indicele elementului cel mai din dreapta;

P2. Dacă x[i]>=v se trece la P5. Altfel se continuă cu pasul următor.

P3. Se incrementează i.

P4. Se continuă cu pasul P2.

P5. Dacă x[j]<=v se trece la pasul P8. Altfel se continuă cu pasul următor.

P6. Se decrementează valoarea lui j.

P7. Se continuă cu pasul P5.

P8. Dacă i>=j, algoritmul se încheie întorcând valoarea lui j.Altfel se continuă cu pasul P9.

P9. Se interschimbă x[i] cu x[j].

P10. Se incrementează i.

P11. Se decrementează j.

P12. Se continuă cu pasul P2.

 

Observaţie1:

         Plasăm pivotul pe prima poziţie deoarece este nevoie să avem certitudinea că acesta se găseşte şi în altă parte decât pe ultima poziţie. Dacă ar fi cel mai mare element din vector, ar fi pus pe ultima poziţie, iar vectorul x[m+1 .. j] ar avea 0 elemente.

 

 Exemplu1:   Fie vectorul de sortat 7, 8, 2, 9, 3.

 

v=7; i=1 ; j=5; 3<=7; deci se interschimbă; i=2; j=4;	i           j 3 8 2 9 7
8>=7 atunci 9<=7 (nu); j=3; 2<=7 (da); le interschimb;i=3; j=2;	i   j                                     3 2 8 9 7
8>=7 atunci 2<=7(da); i>=j STOP RETURNEAZĂ j=2	2 subvectori:   3   2                          8 9 7
a)      v=3; i=1; j=2; 2<=3(da); se interschimbă; i=2; j=1; STOP; b)      v=8; i=3; j=5; 7<=8(da); se interschimbă; i=4; j=4; 9>=8(da); 9<=8(nu); j=3; 7<=8(da); i>=j STOP RETURNEAZĂ j=3	2   3                                                      7   9   8
a)      v=9;  i=4;  j=5; 8<=9(da); se interschimbă; i=5; j=4; 9>=9(da); 8<=9(da); i>=j STOP	2   3                    7                                   8   9
VECTORUL SORTAT:	2  3  7  8  9

 Observaţie2:

     Pentru optimizarea acestei funcţii, la fiecare pas comparăm elementele de pe poziţiile i si j; dacă elementul de pe poziţia i este mai mare decat cel de pe poziţia j, le interschimbăm. Când apare o interschimbare se schimbă şi sensul de parcurgere a şirului. Parcurgerea şirului se începe dinspre dreapta.

Exemplu2:   Fie vectorul de sortat 7, 8, 2, 9, 3.

 

Iniţial i=1 si j=5 şi modul de parcurgere este dinspre dreapta.	i            j                            7 8 2 9 3<=
Se compară 7 cu 3; pentru că 3<7, valorile se vor interschimba; se schimbă modul de parcurgere (i=2).	i        j                         3=>8 2 9 7
Se compară  x[i] cu x[j]; 8>7, este necesară o nouă interschimbare; se schimbă modul de parcurgere (j=4).	i             j                          3 7 2 9 <=8
Se compară  x[i] cu x[j]; 7<9, nu e necesară interschimbarea; j=3;	i   j                          3 7 2<= 9 8
Se compară  x[i] cu x[j]; 7>2, este necesară o nouă interschimbare; se schimbă modul de parcurgere (i=3)	i, j=3 3 2=>  7   9  8
i=j, algoritmul se reia pentru subvectori	3   2    şi  7   9  8

 

Varianta pseudocod a  algoritmului:

 

procedura quick(st , dr);

dacă st

determină prin interschimbări indicele p cu:

• • • st≤p≤dr;
    • oricare ar fi i: st<=i<=p, atunci x[i]<=x[p];
    • oricare ar fi j: p<j<=dr, atunci x[p]>=x[j];

quick(st,p-1);

quick(p+1,dr);

sfârşit dacă;

sfârşit quick;

Observaţie3:

    Pentru împărţirea vectorului în cei doi subvectori, vom folosi funcţia partiţionare, care are ca parametri indicii de început (st) si de sfârşit (dr) ai şirului pentru care se va face poziţionarea şi care returnează poziţia elementului pivot, care va face împărţirea în cei doi subvectori.

        Pentru a simula cele două moduri de deplasare în şir am folosit variabilele di, dj (deplasarea lui i si a lui j). Astfel: 

a.   la parcurgerea dinspre stânga:

-i creşte, deci di=1; 

-j rămâne neschimbat, deci dj=0; 

b.    la  parcurgerea dinspre dreapta:

-i rămâne neschimbat, deci di=0;

-j scade, deci dj=1.

             Atunci când apare o interschimbare a elementelor şirului, modificarea sensului de parcurgere se face interschimbând şi valorile variabilelor di şi dj.

Implementare C++: int x[50],n,i; int partiţionare(int st,int dr){   int aux,i,j,di,dj;  di=0; dj=1; i=st; j=dr;  while(i<j){            if (x[i]>x[j])  {aux=x[i];x[i]=x[j];x[j]=aux;                                aux=di; di=dj; dj=aux; }           i=i+di;           j=j-dj;}   return j;   }  void quick(int st,int dr){   int p;  if (st<dr) {p=partiţionare(st,dr);                   quick(st,p-1);                   quick(p+1,dr);                   }    }    void main(){     cin>>n;    for (i=1;i<=n;i++)cin>>x[i];    quick(1,n);    for (i=1;i<=n;i++)cout<<x[i]<<" "; }

Implementare Pascal: type vector=array [1..50] of integer;  var n,i:integer; x:vector;  function partiţionare(st, dr:integer):integer;  var aux,i,j,di,dj: integer;  begin   di:=0; dj:=1; i:=st; j:=dr;   while i  begin           if x[i]>x[j] then  begin  aux:=x[i]; x[i]:=x[j];x[j]:=aux;                 aux:=di; di:=dj; dj:=aux;                 end;            i:=i+di;           j:=j-dj;           end;   partiţionare:=j;   end;  procedure quick(st,dr:integer);  var p:integer;  begin  if  st  begin  p:=partiţionare(st,dr);                 quick(st,p-1);                 quick(p+1,dr);                  end;    end;  begin  readln(n);  for i:=1 to n do readln(x[i]);  quick(1,n);  for i:=1 to n do writeln(x[i]);  end.

   În cazul cel mai defavorabil, când vectorul x era iniţial ordonat, se fac n-1 apeluri succesive ale procedurii quick, cu parametrii (1, n), (1, n-1), ..., (1, 2) (dacă vectorul x era iniţial ordonat descrescător), respectiv (1, n), (2, n), ..., (n -1, n) (dacă vectorul x era ordonat crescător). La fiecare apel al procedurii quick este apelată funcţia partiţionare(1,i) (respectiv partiţionare(i, n) ) care efectuează i-1, (respectiv n-i-1) operaţii elementare. În total numărul de operaţii elementare este (n-1)+(n-2)+...+1=n×(n-1)/2. Complexitatea algoritmului în cazul cel mai defavorabil este de O(n²). 

      Complexitatea medie a algoritmului QuickSort este O(n log₂n). 

     Sortarea rapidă foloseşte şi un spaţiu de O(n log n) locaţii de memorie, particularitate care-l face să fie printre cei mai utilizaţi algoritmi de sortare. 

     Cea mai complexă problemă în cadrul algoritmului de sortare rapidă o reprezintă alegerea corectă a pivotului, căci corespunzător alegerii corecte a pivotului algoritmul se comportă eficient, iar ineficienţa algoritmului este dată uneori de alegerea necorespunzatoare a pivotului, rezultând o performanţă scazută (O(n²)).  Însă dacă la fiecare pas de sortare se va alege un pivot corect, atunci algoritmul va funcţiona dupa funcţia O(n log₂ n). 

     QuickSort este sensibil la ordinea datelor de intrare. Nu este o metodã stabilã. 

    Cu toate că este un algoritm de sortare foarte rapid, utilizarea QuickSort poate conduce la umplerea stivei atunci când se utilizează seturi largi de date. În plus, datorită complexităţii, algoritmul nu este o alegere practică atunci când se doreşte ordonarea unor seturi de date de dimensiune redusă. 

  QuickSort  reprezintă unul dintre cei mai rapizi algoritmi de sortare. Datorită acestui lucru, algoritmul reprezintă cea mai bună alegere în toate situaţiile în care viteza este foarte importantă, indiferent de dimensiunea seturilor de date ce se doresc a fi sortate. Cu toate acestea nu trebuie scăpat din vedere faptul că algoritmul nu este stabil, iar performanţele acestuia sunt modeste atunci când operează asupra unor liste aproape ordonate.

 Mergi la pagina METODE DE SORTARE

Aplicatii

 

 

Program C++: #include <fstream.h> ifstream fin(“date.in”); ofstream fies(“daet.out”); int poz (int a[1000], int s, int d){ int i, j, di, dj, aux; i=s; j=d; di=0; dj=1; while (i<j){             if(a[i]>a[j]){ aux=a[i]; a[i]=a[j]; a[j]=aux; di=1-di; j=1-dj;} i=i+di; j=j+dj;} return j;} void quicksort (int a[1000], int s, int d){ int p; if (s<d){             p=pos(a,s,d);             quicksort(a,s,p-1);             quicksort(a, p+1, d);} } void citire (int a[1000], int &n){ int i; fin>>n; for (i=1;i<=n;i++) fin>>a[i];} void afis (int a[1000], int n){ int i; for (i=1;i<=n;i++) fies<<a[i]<<’ ‘;} void main(){ int a[1000], n; citire(a,n); quicksort(a,1,n); afis(a,n); }

Program Pascal: PROGRAM QuickSort1; TYPE vector=ARRAY [1..1000] OF INTEGER; VAR a:vector; n: INTEGER; f,g:TEXT; FUNCTION poz (VAR a:vector; VAR s,d:INTEGER):INTEGER; VAR i,j,di,dj,aux; i:=s; j:=d; di:=0; dj:=1; WHILE i             IF a[i]>a[j] THEN BEGIN             aux:=a[i]; a[i]:=a[j];a[j]:=aux;             di:=1-di; dj:=1-dj; END; j:=i+di; j:=j+dj; END; poz:=j; END; PROCEDURE QuickSort(a:vector; s,d:INTEGER); VAR p:INTEGER; BEGIN IF s             P:=poz(a,s,d); QuickSort(a,s,p-1); QuickSort(a,p+1,d); END; END; PROCEDURE citire (VAR a:vector; VAR n:INTEGER); VAR i:INTEGER; BEGIN ASSIGN(f,”date.in”); RESET(F); READ(f,n); FOR i:=1 TO n DO READ(f, a[i]); CLOSE(f)); END; PROCEDURE scriere( a:vector; n:integer); VAR i:INTEGER; BEGIN ASSIGN(g,”date.out”); REWRITE(G); FOR i:=1 TO n DO WRITE(g, a[i]. ‘ ‘); CLOSE(f)); END; BEGIN citire(a,n); QuickSort(a,1,n); scriere(a,n); END.

 

 

Mergi la pagina METODE DE SORTARE

 

 

 

 

•