Sortari (Bubble, Selection, Insertion, Quick, Merge, Heap sort)

Sortarea este operația fundamentală de reordonare a elementelor unui șir (vector, listă) în ordine crescătoare sau descrescătoare, conform unei relații de ordine. În informatică, alegerea algoritmului de sortare influențează direct performanța aplicației, mai ales pentru volume mari de date. La bacalaureat (informatică, clasa a X-a și a XI-a) se studiază atât algoritmi elementari (Bubble, Selection, Insertion) cât și algoritmi avansați (Quick, Merge, Heap).

Bubble Sort (Sortare prin metoda bulelor) – parcurge vectorul repetat, comparând elemente vecine și interschimbându-le dacă sunt în ordinea greșită. Se oprește când nu mai are loc nicio interschimbare. Complexitate O(n²) în cazul mediu și cel mai defavorabil, O(n) dacă vectorul este deja sortat (cu optimizare). Este simplu de implementat, dar ineficient pentru date mari.

Selection Sort (Sortare prin selecție) – la fiecare pas selectează cel mai mic element dintre pozițiile rămase și îl plasează la începutul porțiunii nesortate. Complexitate O(n²) indiferent de datele de intrare. Nu este stabil (nu păstrează ordinea relativă a elementelor egale) dar are un număr minim de interschimbări (cel mult n-1).

Insertion Sort (Sortare prin inserție) – construiește lista sortată câte un element, inserând fiecare element nou în poziția corectă față de elementele deja sortate. Complexitate O(n²) în cazul mediu, dar foarte eficient (O(n)) pentru date aproape sortate. Este stabil și se folosește frecvent ca algoritm auxiliar în sortări hibride.

Quick Sort (Sortare rapidă) – folosește tehnica „divide et impera”: alege un pivot, partiționează vectorul în elemente mai mici și mai mari decât pivotul, apoi sortează recursiv cele două părți. Complexitate medie O(n log n), cel mai defavorabil O(n²) (când pivotul este ales prost). Se implementează cu funcția partition() și se recomandă alegerea pivotului ca mediană a trei elemente pentru evitarea cazului prost.

Merge Sort (Sortare prin interclasare) – tot „divide et impera”: împarte vectorul în jumătăți, le sortează recursiv, apoi interclasează (merge) cele două jumătăți sortate. Complexitate O(n log n) garantată, dar necesită memorie suplimentară O(n). Este stabil și excelent pentru date legate (liste) sau pentru sortare externă.

Heap Sort (Sortare prin heap) – construiește un max-heap (sau min-heap) din vector, apoi extrage succesiv rădăcina (maximul) și o plasează la sfârșit, refăcând proprietatea de heap. Complexitate O(n log n), nu necesită memorie suplimentară (in-place), dar nu este stabil.

Pentru bacalaureat, elevii trebuie să cunoască implementarea în pseudocod sau C++/Pascal a fiecărui algoritm, să analizeze complexitățile și să identifice situațiile în care un algoritm este preferabil altuia. De asemenea, se cere să se aplice algoritmii pe vectori dați, pas cu pas, pentru a verifica înțelegerea corectă a pașilor.

Exemple

• Exemplul 1 – Bubble Sort pas cu pas: Fie șirul [5, 2, 9, 1, 5]. Prima parcurgere: comparăm 5 cu 2 → interschimbăm [2,5,9,1,5]; 5 cu 9 → nu; 9 cu 1 → interschimbăm [2,5,1,9,5]; 9 cu 5 → interschimbăm [2,5,1,5,9]. A doua parcurgere: [2,5,1,5] → (2<5) nu, (5>1) interschimb [2,1,5,5], (5=5) nu → se oprește? Nu, mai avem nevoie de o parcurgere: [2,1] → (2>1) interschimb [1,2,5,5,9]. Șir sortat după 3 parcurgeri.
• Exemplul 2 – Quick Sort: Vector [7, 2, 1, 8, 6, 3, 5]. Alegem pivot primul element (7). Partiția: mutăm elementele mai mici decât 7 la stânga: [2,1,6,3,5] + 7 + [8]. Apoi sortăm stânga recursiv: alegem pivot 2 → [1] +2+ [6,3,5] → sortăm [6,3,5] cu pivot 6 → [3,5] +6 → mai sortăm [3,5] (deja sortat). Dreapta: [8] deja sortat. Rezultat final: [1,2,3,5,6,7,8].
• Exemplul 3 – Merge Sort: Vector [38, 27, 43, 3, 9, 82, 10]. Împărțim: [38,27,43,3] și [9,82,10]. Primul se împarte în [38,27] și [43,3]; apoi [38] [27] → interclasare [27,38]; [43] [3] → interclasare [3,43]; apoi [27,38] cu [3,43] → [3,27,38,43]. Al doilea: [9,82,10] → [9] și [82,10] → [82] [10] → [10,82] → [9,10,82]. Final: interclasare [3,27,38,43] cu [9,10,82] → [3,9,10,27,38,43,82].

Concepte cheie: Stabilitatea sortării: păstrarea ordinii relative a elementelor egale (Insertion, Merge sunt stabile; Selection, Quick, Heap nu sunt), Complexități: O(n²) pentru sortări elementare, O(n log n) pentru sortări avansate, Sortare in-place vs. memorie suplimentară: Quick și Heap sunt in-place, Merge necesită O(n), Tehnica divide et impera aplicată în Quick Sort și Merge Sort, Heap Sort și proprietatea de heap (max-heap și min-heap)