Sortări (Bubble, Insertion, Selection, Merge, Quick, Counting)

Sortarea este una dintre cele mai fundamentale operații în informatică, având rolul de a aranja elementele unui șir (array) într-o ordine specifică (de obicei crescătoare sau descrescătoare). În cadrul Bacalaureatului și al olimpiadelor, elevii trebuie să înțeleagă atât implementarea, cât și complexitatea algoritmilor de sortare.

1. Bubble Sort – Algoritmul parcurge repetat șirul, comparând elemente adiacente și interschimbându-le dacă sunt în ordinea greșită. Procesul se repetă până când șirul este sortat. Complexitatea medie și în cel mai rău caz este O(n^2), iar în cel mai bun caz (șir deja sortat) O(n). Este un algoritm stabil și ușor de înțeles, dar ineficient pentru volume mari de date.

1. Insertion Sort – Se construiește treptat șirul sortat, luând pe rând câte un element din partea nesortată și inserându-l în poziția corectă în partea sortată. Complexitatea medie și în cel mai rău caz este O(n^2), iar în cel mai bun caz O(n). Este stabil și eficient pentru șiruri mici sau aproape sortate.

1. Selection Sort – Se împarte șirul în două părți: una sortată și una nesortată. La fiecare pas, se găsește elementul minim (sau maxim) din partea nesortată și se plasează la sfârșitul părții sortate. Complexitatea este O(n^2) în toate cazurile. Nu este stabil în implementarea standard, dar este simplu și folosește puține interschimbări.

1. Merge Sort – Utilizează metoda divide-et-impera. Șirul este împărțit recursiv în două jumătăți până când fiecare subșir are un element, apoi acestea se interclasează (merge) într-un șir sortat. Complexitatea este O(n log n) în toate cazurile, iar memoria suplimentară este O(n). Este stabil și foarte fiabil, dar necesită spațiu suplimentar.

1. Quick Sort – De asemenea divide-et-impera. Se alege un pivot, se rearanjează șirul astfel încât elementele mai mici decât pivotul să fie în stânga, iar cele mai mari în dreapta, apoi se sortează recursiv părțile. Complexitatea medie este O(n log n), iar în cel mai rău caz O(n^2). Nu este stabil, dar este foarte rapid în practică și folosește spațiu O(log n) pentru stivă.

1. Counting Sort – Este un algoritm de sortare liniară, destinat numerelor întregi dintr-un interval cunoscut (de exemplu, 0..k). Se creează un vector de frecvență, se calculează sume cumulative și apoi se plasează elementele în ordine sortată. Complexitatea este O(n + k), unde k este valoarea maximă. Este stabil și foarte rapid pentru date cu valori mici, dar ineficient pentru intervale mari.

Fiecare algoritm are avantaje și dezavantaje; alegerea depinde de context: dimensiunea datelor, stabilitate, memorie disponibilă.

Exemple

• Exemplul 1 (Bubble Sort): Șirul [5, 2, 9, 1, 5, 6]. Prima parcurgere: 5>2 -> interschimbare [2,5,9,1,5,6]; 5<9 -> nu; 9>1 -> [2,5,1,9,5,6]; 9>5 -> [2,5,1,5,9,6]; 9>6 -> [2,5,1,5,6,9]. A doua parcurgere: 2<5 -> nu; 5>1 -> [2,1,5,5,6,9]; 5=5 -> nu; 5<6 -> nu. A treia parcurgere: 2>1 -> [1,2,5,5,6,9]. Șir sortat.
• Exemplul 2 (Merge Sort): Șirul [38, 27, 43, 3, 9, 82, 10]. Se împarte în [38,27,43,3] și [9,82,10]. Apoi [38,27] și [43,3]; continuă până la elemente individuale. Interclasare: [27,38] cu [3,43] -> [3,27,38,43]; interclasare: [9,10,82]; interclasare finală: [3,9,10,27,38,43,82]. Rezultatul este șirul sortat crescător.
• Exemplul 3 (Counting Sort): Șirul [4, 2, 2, 8, 3, 3, 1]. Valorile sunt între 1 și 8. Se construiește vectorul de frecvență: frec[1]=1, frec[2]=2, frec[3]=2, frec[4]=1, frec[5]=0, frec[6]=0, frec[7]=0, frec[8]=1. Se calculează sume cumulative: 1, 3, 5, 6, 6, 6, 6, 7. Se parcurge șirul original de la dreapta la stânga și se plasează elementele în pozițiile corecte: 1 pe poziția 1, 2 pe pozițiile 2 și 3, 3 pe 4 și 5, 4 pe 6, 8 pe 7.

Concepte cheie: Stabilitatea unui algoritm de sortare, Complexitatea timp (O mare) și spațiu, Divide-et-impera (Merge, Quick) vs sortare prin comparație directă (Bubble, Insertion, Selection), Sortare liniară (Counting) – condiții și limitări, Alegerea algoritmului în funcție de dimensiunea și natura datelor