Sortare prin insertie, selectie, quicksort, mergesort

Sortarea este una dintre cele mai fundamentale operatii in informatica, necesara pentru organizarea eficienta a datelor. In aceasta lectie, vom parcurge patru algoritmi clasici de sortare, analizand principiul de functionare, complexitatea temporala si spatiala, precum si cazurile favorabile, nefavorabile si medii.

1. Sortarea prin insertie (Insertion Sort): Algoritmul construieste treptat un sir sortat, preluand pe rand cate un element din zona nesortata si inserandu-l in pozitia corecta in zona sortata. Initial, primul element este considerat sortat. Pentru fiecare element urmator, se compara cu elementele din zona sortata de la dreapta la stanga, mutandu-le cu o pozitie pana se gaseste locul potrivit. Complexitatea temporala in cazul mediu si defavorabil este O(n^2), iar in cazul favorabil (sir deja sortat) este O(n). Este un algoritm stabil si eficient pentru seturi mici de date sau date aproape sortate.

1. Sortarea prin selectie (Selection Sort): Algoritmul partitioneaza sirul in doua zone: una sortata (la inceput) si una nesortata. La fiecare pas, se cauta elementul minim din zona nesortata si se interschimba cu primul element al acesteia, extinzand astfel zona sortata cu un element. Complexitatea temporala este O(n^2) in toate cazurile, deoarece indiferent de ordinea initiala, se parcurge intotdeauna restul sirului pentru a gasi minimul. Nu este stabil, dar are avantajul unui numar minim de interschimbari (n-1).

1. Quicksort: Este un algoritm de tip divide et impera. Se alege un element numit pivot (de obicei ultimul, primul sau unul aleator). Apoi, sirul se partitioneaza astfel incat elementele mai mici decat pivotul sa fie in stanga, iar cele mai mari in dreapta. Procesul se aplica recursiv pentru sub-sirurile din stanga si dreapta pivotului. In cazul mediu, complexitatea este O(n log n), dar in cazul defavorabil (pivot prost ales, de exemplu sir deja sortat) poate ajunge la O(n^2). Pentru a evita acest lucru, se recomanda alegerea aleatoare a pivotului. Quicksort nu este stabil, dar este extrem de rapid in practica.

1. Mergesort: De asemenea un algoritm divide et impera. Sirul se imparte in mod repetat in doua jumatati pana cand fiecare sub-sir are un singur element (care este implicit sortat). Apoi, sub-sirurile se interclaseaza (merge) in ordine, formand treptat siruri sortate din ce in ce mai mari. Complexitatea temporala este O(n log n) in toate cazurile, ceea ce il face foarte previzibil. Necesita memorie suplimentara O(n) pentru interclasare. Este un algoritm stabil si este preferat atunci cand stabilitatea si performanta constanta sunt esentiale.

Comparatii practice: Pentru seturi mici de date (< 50 elemente), Insertion Sort poate fi mai rapid datorita overhead-ului redus. Quicksort este, in general, cel mai rapid pentru seturi mari, dar poate fi afectat de pivotul prost. Mergesort este preferat pentru date legate (liste inlantuite) sau cand se cere stabilitate.

Exemple

• Exemplul 1: Sortare prin insertie pe sirul [5, 2, 4, 6, 1, 3]. Pas 1: [5] sortat, se ia 2 -> [2,5]. Pas2: [2,5] sortat, se ia 4 -> [2,4,5]. Pas3: [2,4,5] sortat, se ia 6 -> [2,4,5,6]. Pas4: [2,4,5,6] sortat, se ia 1 -> [1,2,4,5,6]. Pas5: [1,2,4,5,6] sortat, se ia 3 -> [1,2,3,4,5,6]. Rezultat final: [1,2,3,4,5,6].
• Exemplul 2: Sortare prin selectie pe sirul [64, 25, 12, 22, 11]. Pas1: minimul din tot sirul este 11, se interschimba cu 64 -> [11,25,12,22,64]. Pas2: minimul din restul [25,12,22,64] este 12, se interschimba cu 25 -> [11,12,25,22,64]. Pas3: minimul din [25,22,64] este 22, se interschimba cu 25 -> [11,12,22,25,64]. Pas4: minimul din [25,64] este 25, ramane neschimbat. Sirul este sortat.
• Exemplul 3: Quicksort pe sirul [3, 7, 8, 5, 2, 1, 9, 5, 4]. Alegem pivot = 4 (ultimul). Dupa partitionare: elemente < 4: [3,2,1], pivot = 4, elemente > 4: [7,8,5,9,5]. Aplicam recursiv pe stanga: [3,2,1] pivot=1 -> [1,2,3]; pe dreapta: [7,8,5,9,5] pivot=5 -> [5,5,7,8,9]. Interclasam: [1,2,3,4,5,5,7,8,9].

Concepte cheie: Insertion Sort: O(n^2) in caz mediu, O(n) in caz favorabil, stabil, Selection Sort: O(n^2) in toate cazurile, instabil, Quicksort: O(n log n) in caz mediu, O(n^2) in caz defavorabil, instabil, pivotul este crucial, Mergesort: O(n log n) in toate cazurile, stabil, necesita memorie suplimentara O(n), Divide et impera: Quicksort si Mergesort se bazeaza pe aceasta tehnica, Stabilitatea unui algoritm de sortare pastreaza ordinea relativa a elementelor cu chei egale