Algoritmi de sortare

Sortarea este o operaţie fundamentală în informatică, mulţi algoritmi o folosesc ca pas intermediar, are o largă aplicabilitate în informatică şi disciplinele conexe. Studierea metodelor de sortare este de o mare importanţă. Orice algoritm de sortare are scopul de a oferi o soluție reprezentând o reordonare a unui șir de numere:

Intrare: Un şir de n numere (a1, a2, …, an).

Ieşire: O permutare (reordonare) (a’1, a’2, …, a’n) a şirului dat astfel încât a’1≤ a’2≤ …≤a’n.

Şirul de intrare este, de obicei, un tablou cu n elemente, deşi el poate fi reprezentat şi în alt mod, de exemplu sub forma unei liste înlănţuite.

Numim sortare orice aşezare (sau - mai clar - reaşezare) a unor elemente date în aşa fel încât, după aşezare, să existe o ordine completă în funcţie de un atribut (numit cheie) al elementelor. Pentru a exista o ordine completă, trebuie să alegem o relaţie pe care vrem să o impunem. Dacă relaţia este valabilă între oricare două elemente pentru care primul element este aşezat la stânga celui de-al doilea, atunci avem o ordine completă. Spre exemplu, dacă alegem drept cheie un atribut număr întreg şi relaţia mai mic sau egal(<=), obţinem ordinea crescătoare.

În practică, numerele care trebuie ordonate sunt rareori valori izolate. De obicei, fiecare număr face parte dintr-o colecţie de date numită articol. Fiecare articol conţine o cheie, care este valoarea ce trebuie ordonată, iar restul articolului conţine date adiţionale, care sunt, de obicei, mutate împreună cu cheia. În practică, atunci când un algoritm de ordonare interschimbă cheile, el trebuie să interschimbe şi datele adiţionale. Dacă fiecare articol include o cantitate mare de date adiţionale, de multe ori interschimbăm un tablou de pointeri la articole, în loc să interschimbăm articolele înseşi, cu scopul de a minimiza cantitatea de date care este manevrată.

Dintr-un anumit punct de vedere, tocmai aceste detalii de implementare disting un algoritm de programul propriu-zis. Faptul că sortăm numere individuale sau articole mari, ce conţin numere, este irelevant pentru metoda prin care o procedură de ordonare determină ordinea elementelor. Astfel, atunci când ne concentrăm asupra problemei sortării, presupunem, de obicei, că intrarea constă numai din numere. Implementarea unui algoritm care sortează numere este directă din punct de vedere conceptual, deşi, într-o situaţie practică dată, pot exista şi alte subtilităţi care fac ca implementarea propriu-zisă a algoritmului să fie o sarcină dificilă.

Analiza complexității unui algoritm are ca scop estimarea volumului de resurse de calcul necesare pentru execuția algoritmului. Prin resurse se înțelege: 

• Spațiul de memorie necesar pentru stocarea datelor pe care le prelucrează algoritmul. 

• Timpul necesar pentru execuția tuturor prelucrărilor specificate în algoritm.

Această analiză este utilă pentru a stabili dacă un algoritm utilizează un volum acceptabil de resurse pentru rezolvarea unei probleme. În acest fel timpul de execuție va fi exprimat prin numărul de operații elementare executate. Sunt considerate operații elementare cele aritmetice (adunare, scădere, înmulțire, împărțire), comparațiile și cele logice (negație, conjuncție și disjuncție).

Așadar, este suficient să se contorizeze doar anumite tipuri de operații elementare, numite operații de bază. Timpul de execuție al întregului algoritm se obține însumând timpii de execuție ai prelucrărilor componente.

Au fost inventaţi un număr foarte mare de algoritmi diferiţi pentru sortarea unui vector, însă, deşi diferiţi, sunt legaţi între ei şi nu sunt greu de învăţat. În cartea lui D. Knuth „Arta programării calculatoarelor”, vol. III (Căutări şi ordonări) sunt prezentate 33 de metode de ordonare. O parte vor fi prezentate în această lucrare. Este indicat să cunoaştem caracteristicile fiecărei metode de sortare, ca să fim în măsură să facem alegeri în cunoştinţă de cauză pentru aplicaţii particulare.

Tehnicile de sortare se pot clasifica în mai multe feluri, în funcţie de complexitate, de cantitatea de memorie necesară. Iată câteva clasificări: 

După cantitatea de memorie utilizată:

a) metode directe (sortează vectorul în spaţiul său de memorie)

b) metode indirecte (necesită vector auxiliar)

După spaţiul de memorie utilizat:

a) metode interne (ordonează tablouri în memoria internă)

b) metode externe (ordonează sau interclasează fişiere din memoria externă)

După ordinul de complexitate:

a) metode liniare

b) metode pătratice

c) metode n*log2n

O altă clasificare poate fi făcută după dificultatea algoritmilor implicaţi: 

a) metode simple - se bazează pe algoritmi de dificultate redusă (inserţie, selecţie, metoda bulelor), dar mai puţin eficiente. 

b) metodele avansate - se bazează pe algoritmi puţin mai complicaţi, care necesită mici “artificii” pentru a realiza ordonarea (quicksort, sortarea prin interclasare, heap-sort), dar care sunt mai eficiente decât cele directe.