Introducere in Stiinta Calculatoarelor 2013 | Page 90
Sortare rapidă
În multe cazuri piesele de date trebuie aranjate în ordine crescătoare
(sortate ascendent) sau descrescătoare (sortate descendent) – vezi cazul
listei- funcţie de un criteriu de ordine (numeric sau alfabetic lexicografic). Astfel, sortarea este o prelucrare des întâlnită şi, ca atare,
necesită metode rapide de execuţie. Există o serie de metode de sortare,
între care amintim: „metoda bulelor”, „metoda inserţiei”, „metoda
selecţiei”. În cele ce urmează, se prezintă o „metoda rapidă” de sortare
(denumită „quicksort”), care este mult mai rapidă faţă de alte metode
(cum sunt metoda selecţiei, metoda inserţiei, faţă de care este de 100,
respectiv de 20 de ori mai rapidă).
Sortarea rapidă se bazează pe înjumătăţire, rearanjând elementele prin
comparaţii între mijlocul listei şi capetele acesteia, apoi procedând
similar cu jumătăţile obţinute până la ordonarea completă a listei.
Algoritmul poate fi realizat recursiv, deci permite o scriere compactă şi
elegantă.
Se consideră ca variabile: Lista (ca vector conţinând elementele de
sortat – în care un element în poziţia i este referit prin indexul său, adică
Lista[i], apoi în lista curentă: indicele inferior (primul element) Iinf,
indicele superior (ultimul element) Isup, doi indici de lucru i şi j, apoi
elementul pivot (elementul de la mijlocul listei) Pivot. Funcţia
Inversează() inversează elementele de pe poz iţiile specificate ca
parametri.
SortareRapida(Iinf, Isup)
{
i=Iinf; j=Isup;
Pivot=Lista[(Iinf+Isup)/2];
do
{
while(Lista[i]