Informatică Algoritmi
Sortarea rapida quicksort explicata
Sortarea rapidă Quicksort este un algoritm de sortare bazat pe principiul divide et impera, care alege un element pivot și împarte vectorul în două părți: elemente mai mici decât pivotul și elemente mai mari.
Pașii algoritmului Quicksort
- 1 Alegerea pivotului Selectează un element din vector ca pivot; de obicei primul, ultimul sau unul aleatoriu.
- 2 Partiționarea Rearanjează vectorul astfel încât toate elementele mai mici decât pivotul să fie în stânga, iar cele mai mari în dreapta; pivotul ajunge în poziția sa finală.
- 3 Apel recursiv Aplică recursiv Quicksort pe subvectorul din stânga și pe cel din dreapta pivotului.
- 4 Caz de bază Opriți recursivitatea când subvectorul are 0 sau 1 element, deoarece este deja sortat.
Exemplu numeric
- Vector inițial [5, 2, 9, 1, 5, 6]; alegem pivotul 5 (ultimul element).
- După partiționare [2, 1, 5, 5, 9, 6]; pivotul 5 este la poziția corectă, cu elemente mai mici în stânga și mai mari în dreapta.
- Sortare recursivă Aplică Quicksort pe [2, 1] și [9, 6]; rezultat final: [1, 2, 5, 5, 6, 9].
Folosește Quicksort pentru sortare rapidă în practică, dar testează cu diferite pivoturi pentru a evita cazurile cele mai proaste.