Informatică Algoritmi
Algoritmi de sortare avansati quicksort mergesort
Quicksort și Mergesort sunt doi algoritmi de sortare avansați care folosesc strategia divide et impera. Quicksort alege un pivot și partitionează lista, iar Mergesort împarte lista în jumătăți și o reunește sortată. Ambii au complexitate medie O(n log n).
Quicksort - algoritmul
- 1 Alegerea pivotului Se alege un element din listă ca pivot (de exemplu, primul, ultimul sau medianul).
- 2 Partiționarea Se rearanjează lista astfel încât elementele mai mici decât pivotul să fie în stânga și cele mai mari în dreapta.
- 3 Apel recursiv Se aplică recursiv quicksort pe subliste din stânga și dreapta pivotului.
Mergesort - caracteristici
- Divizare Lista este împărțită recursiv în subliste de dimensiune 1 sau 0.
- Îmbinare Sublistele sunt reunite într-o listă sortată, comparând elementele pe rând.
- Stabilitate Mergesort este un algoritm stabil, păstrând ordinea elementelor egale.
Pentru liste mari, alege Mergesort dacă ai nevoie de stabilitate, sau Quicksort pentru viteza medie superioară.