Sortarea rapidă
Sortarea rapidă este un experiment interactiv din Algoritmi în acțiune, o simulare gratuită din StudyFi Lab care rulează direct în browser.
Sortarea rapidă alege un pivot — aici ultimul element al secvenței (partiționarea Lomuto) — și rearanjează secvența astfel încât elementele mai mici să ajungă la stânga, iar restul la dreapta. Pivotul ajunge astfel pe locul lui final, iar cele două părți se sortează la fel. În medie este O(n log n), dar când pivotul împarte prost (de exemplu la un tablou deja sortat sau inversat) scade la O(n²).
Încearcă: Compară o intrare aleatoare cu una inversată. La tabloul inversat pivotul este mereu cel mai mare sau cel mai mic — urmărește cum sare numărul de comparații.
Întrebări frecvente
Ce arată experimentul „Sortarea rapidă”?
Sortarea rapidă alege un pivot — aici ultimul element al secvenței (partiționarea Lomuto) — și rearanjează secvența astfel încât elementele mai mici să ajungă la stânga, iar restul la dreapta. Pivotul ajunge astfel pe locul lui final, iar cele două părți se sortează la fel. În medie este O(n log n), dar când pivotul împarte prost (de exemplu la un tablou deja sortat sau inversat) scade la O(n²).
Cum încerc „Sortarea rapidă”?
Compară o intrare aleatoare cu una inversată. La tabloul inversat pivotul este mereu cel mai mare sau cel mai mic — urmărește cum sare numărul de comparații.
Înveți pentru un test?
Încarcă-ți notițele și StudyFi le transformă în flashcarduri, teste și podcasturi.