SORTARE RAPIDA (QUICK SORT)

În sortarea rapida este folosită metoda divide et impera. Mai departe este explicată varianta recursivă:

1. Se alege o valoare pivot. Se ia valoarea elementului din mijloc ca valoare pivot, dar poate fi oricare altă valoare, care este în intervalul valorilor sortate, chiar dacă nu este prezentă în tablou.

2. Partiţionare, Se rearanjează elementele în aşa fel încât, toate elementele care sunt mai mari decât pivotul merg în partea dreaptă a tabloului. Valorile egale cu pivotul pot sta în orice parte a tabloului. Putem observa ca tabloul poate fi împărţit în părţi care nu au aceeaşi dimensiune ( adica nu sunt egale).

3. Se sortează amândouă părţile aplicându-se recursiv algoritmul de sortare rapidă în partea dreaptă şi în partea stângă.

Algoritmul de partiţie în detaliu.

Există 2 indici i şi j, şi la începutul algoritmului de partiţionare i indică primul element al tabloului iar j indică ultimul element din tablou. La următorul pas algoritmul mută i înainte, până când un element cu o valoare mai mare sau egală cu pivotul este găsită. Indicele j este mutat înapoi, pâna când un element cu valoare mai mică sau egală cu pivotul este găsită. Dacă i<=j atunci i merge pe poziţia i+1 iar j merge pe poziţia j-1. Algoritmul se opreşte, când i devine mai mare decât j.

Exemplu:

Dorim să sortăm şirul {1, 13, 7, 28, 10, 16, 3, 10, 2} folosind sortarea rapidă.

1, 13, 7, 28, 10, 16, 3, 10, 2 - nesortat

1, 13, 7, 28, 10, 16, 3, 10, 2 - valoarea pivot = 10

1, 13, 7, 28, 10, 16, 3, 10, 2 - 13 >= 10 >= 2, interschimbăm 13 cu 2

1, 2, 7, 28, 10, 16, 3, 10, 13 - 28 >= 10 >= 10 , interschimbăm 28 cu 10

1, 2, 7, 10, 10, 16, 3, 28, 13 - 10 >= 10 >= 3, interschimbăm 10 cu 3

1, 2, 7, 10, 3, 16, 10, 28, 13 - i > j, se opreşte partiţionarea

se aplică din nou algoritmul pentru șirul {1, 2, 7, 10, 3 si 16, 10, 28, 13} până când se va obține șirul {1, 2, 3, 7, 10, 10, 13, 16, 28} – şir sortat.

Algoritm descris în pseudocod:

QuickSort(V,st,dr);

pivot←v[(st+dr) div 2)];

cât timp i<=j execută

cât timp v[i] <pivot execută i←i+1;

sfcăt timp

cât timp v[j] >pivot execută j←j-1;

sfcăt timp

dacă i<=j atunci

aux←v[i];v[i]←v[j];v[j]←aux;i←i+1;j←j-1;

sfdacă

sfcăt timp

dacă st<j atunci quikSort(v,st,j);

sfdacă

dacă i<dr atunci quikSort(v,i,dr);

sfdacă

sfQuickSort

Implementare în C++

void quickSort(int v[],int st, int dr)

{

int i=st,j=dr;int aux; int pivot=v[(st+dr)/2];

while(i<=j)

{ while (v[i]<pivot)

i++;

while(v[j]>pivot)

j--;

if (i<=j)

{ aux=v[i];

v[i]=v[j];

v[j]=aux;

i++;

j--;

}

}

if (st<j)

quickSort(v,st,j);

if (i<dr)

quickSort(v,i,dr);

}