Informatică Algoritmi
Algoritmi de sortare eficienti Quicksort Mergesort
Quicksort și Mergesort sunt algoritmi de sortare eficienți cu complexitate medie O(n log n), folosiți pentru liste mari. Quicksort folosește o strategie divide et impera cu un pivot, iar Mergesort împarte lista în jumătăți și le interclasează.
Quicksort
- 1 Pasul 1 Alege un element pivot din listă (de ex., primul sau mijlocul).
- 2 Pasul 2 Rearanjează lista astfel încât elementele mai mici decât pivotul să fie în stânga, iar cele mai mari în dreapta.
- 3 Pasul 3 Aplică recursiv Quicksort pe subliste din stânga și dreapta pivotului.
Mergesort și comparație
- Mergesort Împarte lista în două jumătăți egale, sortează fiecare recursiv, apoi interclasează jumătățile sortate.
- Complexitate Ambele au O(n log n) în medie, dar Quicksort are O(n²) în cazul cel mai rău, Mergesort are O(n log n) garantat.
- Exemplu numeric Pentru lista [3, 1, 4, 2], Quicksort cu pivot 3: [1, 2] și [4], apoi sortează; Mergesort: împarte în [3,1] și [4,2], sortează și interclasează.
Alege Quicksort pentru viteza practică și Mergesort pentru stabilitate și performanță garantată.