Algoritmi de sortare și căutare

Elevii studiază principalii algoritmi de sortare și căutare și le analizează eficiența.

De ce sortăm și ce înseamnă o sortare

A sorta un vector înseamnă a-i rearanja elementele în ordine crescătoare sau descrescătoare. Sortarea e una dintre cele mai studiate probleme din informatică pentru că datele ordonate se prelucrează incomparabil mai ușor: minimul e primul element, maximul e ultimul, valorile egale stau grupate, iar căutarea binară devine posibilă.

Toate metodele studiate în gimnaziu au același schelet: comparații între elemente și interschimbări (schimbarea a două valori între ele, cu variabilă auxiliară: aux = v[i]; v[i] = v[j]; v[j] = aux;).

Ce le deosebește este STRATEGIA — cine cu cine se compară și când se mută:

• selecția: caut minimul din zona nesortată și îl aduc pe poziția curentă;
• inserția: iau următorul element și îl strecor la locul potrivit în zona deja sortată;
• interschimbarea (bubble sort): compar mereu vecini și îi schimb dacă sunt în ordine greșită.

Pentru a sorta descrescător, nu inventezi altă metodă — inversezi doar sensul comparației (cauți maximul în loc de minim, schimbi vecinii când cel din stânga e mai MIC).

La evaluare, cerința tipică nu e să scrii sortarea din memorie, ci să urmărești ce conține vectorul după un anumit număr de pași sau treceri — de aceea trebuie să știi exact ce garantează fiecare metodă după fiecare etapă.

Sortarea prin selecție

Ideea selecției e cea mai naturală: la fiecare pas selectezi minimul din porțiunea rămasă nesortată și îl aduci la începutul ei.

Pașii pentru un vector cu n elemente:

• Pasul 1: găsești minimul dintre v[1]...v[n] și îl interschimbi cu v[1]. Acum v[1] e definitiv la locul lui.
• Pasul 2: găsești minimul dintre v[2]...v[n] și îl interschimbi cu v[2].
• ... și tot așa până la pasul n−1; ultimul element rămâne automat pe poziția corectă.

Garanția-cheie, care se cere la itemii de urmărire: după pasul k, primele k elemente sunt cele mai mici k valori ale vectorului, deja în ordine finală. Zona din stânga e „închisă” — nu se mai atinge.

Exemplu pe v = (5, 2, 4, 1): după pasul 1 → (1, 2, 4, 5)... atenție, să-l facem corect: minimul e 1, se interschimbă cu 5 → (1, 2, 4, 5). Aici vectorul arată sortat din întâmplare, dar algoritmul CONTINUĂ mecanic pașii 2 și 3, chiar dacă nu mai schimbă nimic — algoritmii nu „văd” că au terminat, execută toți pașii prescriși.

Numărul de comparații nu depinde de datele inițiale: mereu (n−1) + (n−2) + ... + 1 comparații, aproximativ n·n/2 — deci selecția e la fel de „lentă” și pe un vector deja sortat. În schimb, numărul de INTERSCHIMBĂRI e mic: cel mult una pe pas, maximum n−1 în total — punct forte al metodei.

Sortarea prin inserție

Inserția funcționează exact cum îți aranjezi cărțile de joc în mână: ții în stânga o parte deja ordonată și fiecare carte nouă o strecori la locul ei.

Pașii: presupui că v[1] formează singur o zonă sortată. Iei pe rând v[2], v[3], ..., v[n]; pe fiecare îl compari cu vecinii din zona sortată, deplasezi spre dreapta elementele mai mari decât el și îl inserezi în golul creat.

Exemplu pe v = (4, 3, 5, 1):

• inserăm 3 în zona (4): 4 se deplasează, obținem (3, 4, 5, 1);
• inserăm 5 în zona (3, 4): 5 e deja mai mare decât 4, rămâne pe loc → (3, 4, 5, 1);
• inserăm 1 în zona (3, 4, 5): toate se deplasează → (1, 3, 4, 5).

Diferența subtilă față de selecție, vânată la teste: după pasul k, la inserție primele k elemente sunt ordonate între ele, dar NU sunt neapărat cele mai mici k valori din vector (în exemplu, după pasul 2 zona sortată era (3, 4, 5), dar valoarea 1 — cea mai mică — încă aștepta afară). La selecție, zona sortată conține garantat cele mai mici valori, în poziții definitive.

Eficiența inserției depinde de date: pe un vector deja sortat face doar n−1 comparații și nicio deplasare — cel mai bun caz; pe un vector sortat invers face maximum de muncă. De aceea inserția e preferată când datele sunt „aproape sortate”.

Sortarea prin interschimbare (bubble sort)

Metoda bulelor compară mereu perechi de elemente vecine: dacă v[i] > v[i+1], le interschimbă. O trecere completă prin vector plimbă valorile mari spre dreapta — cea mai mare valoare „urcă” precum o bulă de aer până pe ultima poziție.

Garanția după fiecare trecere: la finalul trecerii k, ultimele k elemente sunt cele mai mari k valori, definitiv așezate. Zona finală se construiește de la coadă spre început — invers față de selecție.

Algoritmul se oprește când o trecere întreagă se încheie fără nicio interschimbare — semn că vectorul e sortat. Implementarea folosește o variabilă-semafor (de exemplu ok): o pui pe „adevărat” la începutul trecerii și o faci „fals” la orice interschimbare; repeți trecerile cât timp s-a schimbat ceva.

Exemplu, o trecere pe v = (3, 1, 4, 2):

• comparăm 3 și 1 → schimb → (1, 3, 4, 2);
• comparăm 3 și 4 → ordine bună, nimic;
• comparăm 4 și 2 → schimb → (1, 3, 2, 4).

După prima trecere, 4 (maximul) e definitiv pe ultima poziție, dar vectorul NU e încă sortat — mai e nevoie de o trecere pentru perechea (3, 2). Întrebarea-capcană standard: „este vectorul sortat după o singură trecere?” — de regulă NU; o trecere garantează doar poziția maximului.

Pe vector deja sortat, bubble sort cu semafor face o singură trecere de verificare și se oprește — avantaj față de selecție.

Căutarea secvențială și căutarea binară

Căutarea secvențială (liniară) parcurge vectorul element cu element și compară fiecare valoare cu cea căutată. Se oprește la prima potrivire sau după ultimul element. Funcționează pe orice vector, sortat sau nu. În cel mai rău caz (element pe ultima poziție sau inexistent) face n comparații.

Căutarea binară cere OBLIGATORIU vector sortat — condiție care se pierde des din vedere și costă punctajul întreg. Mecanismul: ții două capete, st și dr; calculezi mijlocul m = (st + dr) / 2; compari v[m] cu valoarea căutată x:

• v[m] = x → găsit, stop;
• v[m] < x → x nu poate fi decât în dreapta: st = m + 1;
• v[m] > x → x nu poate fi decât în stânga: dr = m − 1.

Repeți cât timp st <= dr; dacă intervalul se golește, x nu există în vector.

Exemplu pe v = (2, 5, 8, 11, 14, 17, 20), căutăm 17: mijlocul e 11 → 17 > 11, mergem în dreapta; noul mijloc e 17 → găsit în 2 comparații, față de 6 la secvențială.

Puterea metodei: fiecare comparație înjumătățește intervalul, deci pentru n = 1000 ajung circa 10 comparații, pentru un milion — circa 20. Dublarea datelor adaugă O SINGURĂ comparație în plus.

Judecata de eficiență cerută la subiecte: dacă faci o singură căutare într-un vector nesortat, secvențiala e alegerea corectă (sortarea ar costa mai mult decât economisește); dacă faci MULTE căutări, merită să sortezi o dată și apoi să cauți binar.

Test — 6 întrebări ca la examen