Quicksort
(algortim)
Quicksort este un algortim de sortare inventat de Tony Hoare in 1960 si este unul ditre cei mai utilizati algortimi de sortare, in practica.
Practic, algoritmul presupune alegera unui element din lista pe care vrem sa o sortam si sa plasam elementele mai mici ca acel element(i se mai sune si pivot) in stanga lui, iar pe cele mai mari in dreapta lui. Dupa acest pas, pivotul, adica elementul ales mai devreme, se afla pe pozitia lui finala - adica in lista sortata pivotul se va gasi tot pe aceasta pozitie.
Sa luam un exemplu:
9, 4, 5, 3, 1, 10
Pentru acest tutorial ne vom limita la varianta de quicksort ce foloseste pivot ales din mijlocul listei. Pivotul nostru este 5. Acum vom plasa elementle mai mici decat pivotul, adica 5, in stanga lui, iar elementele mai mari ca acesta in drapta lui.
1, 4, 3, 5, 10, 9
Dupa cum vedeti, pivotul a ajuns in pozitia lui finala. Atunci cand lista va fi sortata pivotul, adica 5, va ramane tot pe poztia in care se afla acum.
Acest pas de "triere" a elementelor unei liste in functie de un pivot se numeste partitionare. In acest pas singurul lucru care ne intereseaza este sa plasm elementele mai mici dacat pivotul in stanga lui iar pe cele mai mari ca el in dreapta lui. Nu ne intereseaza daca elemntele ce au fost plasate in dreapta sau stanga pivotului se afla in ordine.
Probabil te intrebi de ce am pus in stanga lui 5 elementele 1, 4, 3 si de ce nu 1, 3, 4? Tot ce am vrut prin acel exemplu era sa-ti arat ca la partitionarea listei singurul lucru care conteaza este sa plasam elementle mai mari ca pivotul in dreapta si cele mai mici ca el in stanga, nu are nicio importanta daca acestea se afla in ordine sau nu.
Dupa ce am partitionat lista se poate observa ca avem acum doua subliste: cea formata din elementele din stanaga pivotului si cea formata din elementele din dreapta pivotului. Tot ce avem acum de facut este sa partitionam acum fiecare sublista in parte, iar, dupa acest pas, sa partitionam subsubliste ce sau format din sublistele formate din lista initiala.
Acest proces recursiv de partitionare a sublistelor formate din lista initiala se numeste reprezinta quicksort. Ca orice alt algoritm recursiv, quicksort, cazul de baza a lui quicksort este atunci cand lista contine 1 sau 0 elemente. In acest caz nu se mai face partitionarea, pentru ca nu se poate sa ai dezordine intr-o lista cu doar un sigur element.
Rezumand ce am spus mai sus reiese urmatoarea schita:
1) partitionarea listei
2) partitionarea recursiva a sublistelor formate pana la atingerea cazului de baza
