Informatică Algoritmi
Algoritmi de sortare rapida Quicksort
Quicksort este un algoritm de sortare eficient bazat pe principiul divide et impera. El alege un element pivot și împarte vectorul în două părți: elemente mai mici decât pivotul și elemente mai mari. Apoi sortează recursiv cele două părți.
Pași algoritmului Quicksort
- 1 Alegerea pivotului Selectează un element din vector ca pivot (de obicei primul, ultimul sau mediana).
- 2 Partiționarea Rearanjează vectorul astfel încât elementele mai mici decât pivotul să fie în stânga, iar cele mai mari în dreapta.
- 3 Apel recursiv Aplică Quicksort recursiv pe subvectorul din stânga și pe cel din dreapta pivotului.
Exemplu numeric
- Vector inițial [5, 2, 9, 1, 5, 6]
- Pivot (ultimul element) 6
- După partiționare [5, 2, 1, 5, 9, 6]
- Sortează recursiv Aplică Quicksort pe [5, 2, 1, 5] și pe [9].
Folosește Quicksort pentru sortări rapide în practică, dar testează cu diferite pivoturi pentru a evita cazurile cele mai proaste.