Scribd
Încărcați
6 vizualizări2 pagini

Quick Sort

QuickSort este un algoritm de sortare eficient, dezvoltat de C.A.R. Hoare în 1960, cu o complexitate medie de O(n log n) și O(n²) în cel mai rău caz. Algoritmul utilizează tehnica divide et impera, alegând un pivot pentru a organiza elementele dintr-un tablou în funcție de acesta. Performanța sa depinde de alegerea pivotului și de echilibrul secvențelor rezultate, iar metodele de selecție a pivotului pot îmbunătăți eficiența în cazuri specifice.

Încărcat de

carmenantohe
Drepturi de autor
© All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca PDF, TXT sau citiți online pe Scribd
6 vizualizări2 pagini

Quick Sort

QuickSort este un algoritm de sortare eficient, dezvoltat de C.A.R. Hoare în 1960, cu o complexitate medie de O(n log n) și O(n²) în cel mai rău caz. Algoritmul utilizează tehnica divide et impera, alegând un pivot pentru a organiza elementele dintr-un tablou în funcție de acesta. Performanța sa depinde de alegerea pivotului și de echilibrul secvențelor rezultate, iar metodele de selecție a pivotului pot îmbunătăți eficiența în cazuri specifice.

Încărcat de

carmenantohe
Drepturi de autor
© All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca PDF, TXT sau citiți online pe Scribd

QuickSort sau Sortarea rapidă este o metodă eficientă de sortare a unui tablou, descoperită în

1960 de programatorul britanic C.A.R. Hoare. Pentru un set de n valori oarecare algoritmul
efectuează O(nlogn)�(�log⁡�) comparații, dar în cazul cel mai nefavorabil se
efectuează O(n2)�(�2) comparații.
Algoritmul este de tip divide et impera; el sortează o secvență a tabloului (inițial întreg tabloul),
astfel:

• se alege un element special al listei, numit pivot;


• se ordonează elementele listei, astfel încât toate elementele din stânga pivotului să fie mai
mici sau egale cu acesta, și toate elementele din dreapta pivotului să fie mai mari sau
egale cu acesta;
• se continuă recursiv cu secvența din stânga pivotului și cu cea din dreapta lui.

Următoarea funcție C++ realizează sortarea unui tablou, transmis ca parametru:

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


{
if(st < dr)
{
//pivotul este inițial v[st]
int m = (st + dr) / 2;
int aux = v[st];
v[st] = v[m];
v[m] = aux;
int i = st , j = dr, d = 0;
while(i < j)
{
if(v[i] > v[j])
{
aux = v[i];
v[i] = v[j];
v[j] = aux;
d = 1 - d;
}
i += d;
j -= 1 - d;
}
QuickSort(v, st , i - 1);
QuickSort(v, i + 1 , dr);
}
}

Observații:

• în timpul pivotării:
o la fiecare iterație, doar una dintre variabilele i și j se modifică: sau crește i, sau
scade j
o pivotul este elementul cu indicele care nu se modifică
• algoritmul descris mai sus realizează ordonarea crescătoare a tabloului; pentru ordonarea
descrescătoarea algoritmul este asemănător: prin pivotare, elementele din stânga
pivotului devin mai mari decât acesta, cele din dreapta devin mai mici;
• algoritmul este cu atât mai rapid cu cât la fiecare etapă cele două secvențe delimitate de
pivot au lungimi cât mai apropiate (ideal egale);
• dacă tabloul este de a început ordonat crescător sau descrescător, complexitatea
algoritmului devine pătratică – O(n2)�(�2);
• anumite metode de alegere a pivotului pot să evite această situație

S-ar putea să vă placă și