Algoritmi de sortare și căutare
Analiza și implementarea algoritmilor clasici de sortare și căutare.
Bacalaureat
Sortările elementare: selecție, inserție, bule
Sortările elementare au complexitate O(n²) și se cer la examen mai ales ca simulare pas cu pas — trebuie să știi exact cum arată vectorul după fiecare etapă.
- Sortarea prin selecție: la pasul i se caută minimul din zona nesortată v[i..n-1] și se interschimbă cu v[i]. După pasul i, primele i+1 elemente sunt definitiv pe pozițiile lor finale. Face puține interschimbări (cel mult n-1), dar mereu același număr de comparații, indiferent dacă vectorul e deja sortat.
- Sortarea prin inserție: la pasul i, elementul v[i] se inserează la locul potrivit în zona deja sortată v[0..i-1], deplasând spre dreapta elementele mai mari. Pe un vector aproape sortat e foarte rapidă — cazul favorabil este O(n); acesta e detaliul care o diferențiază la grile.
- Sortarea prin interschimbare (bubble sort): se compară repetat elemente vecine și se interschimbă dacă sunt în ordine greșită, până la o parcurgere completă fără nicio interschimbare. După prima parcurgere, maximul ajunge garantat pe ultima poziție.
Capcana de simulare: la selecție, după pasul i prefixul e format din elementele finale; la inserție, prefixul e sortat, dar provizoriu — pot intra ulterior elemente mai mici în el. Confundarea celor două tablouri intermediare e cea mai comună sursă de răspunsuri greșite.
Sortarea prin numărare și limitele ei
Sortarea prin numărare (counting sort) nu compară elementele între ele: pentru fiecare valoare posibilă se numără aparițiile într-un vector de frecvență, apoi vectorul sortat se reconstruiește parcurgând frecvențele în ordine.
Pașii pentru un vector cu valori întregi din intervalul [0, k]:
- se construiește vectorul de frecvență f[0..k], unde f[x] = de câte ori apare valoarea x;
- se parcurge f de la 0 la k și se scrie fiecare valoare x de f[x] ori în vectorul rezultat.
Complexitatea este O(n + k) — liniară, mai bună decât orice sortare prin comparații, care nu poate coborî sub O(n log n) în cazul general. Dar avantajul vine cu restricții care se cer explicit la examen:
- valorile trebuie să fie întregi (sau discretizabile) și cuprinse într-un interval cunoscut și rezonabil de mic; pentru valori până la un miliard, vectorul de frecvență nu încape în memorie;
- memoria suplimentară este O(k) — sortarea nu e „pe loc”.
O variantă des întâlnită în subiecte: numărarea aparițiilor cifrelor sau a literelor (k = 10, respectiv 26), unde metoda e imbatabilă. Confuzia frecventă: elevii aplică mecanic counting sort la numere reale sau la intervale uriașe — enunțul care precizează „numere naturale cel mult 100” este semnalul că asta e metoda așteptată.
QuickSort: partiționare în jurul pivotului
QuickSort este o aplicare a metodei Divide et Impera:
- se alege un pivot din vector;
- se partiționează vectorul: la stânga pivotului ajung elementele mai mici, la dreapta cele mai mari — după partiționare, pivotul se află pe poziția sa finală;
- se sortează recursiv cele două zone; nu există pas de combinare — vectorul e sortat când toate apelurile s-au terminat.
Complexități, întrebare de teorie garantată:
- cazul mediu și cel favorabil: O(n log n) — pivotul împarte vectorul în părți echilibrate;
- cazul defavorabil: O(n²) — pivotul e mereu minimul sau maximul zonei, iar partiționarea produce o parte cu un singur element; asta se întâmplă tipic la un vector deja sortat, cu pivotul ales ca prim sau ultim element.
Detaliul contraintuitiv care se punctează: QuickSort e „rapid” în medie, dar are cel mai prost caz mai slab decât MergeSort. În schimb sortează pe loc (nu cere vector auxiliar semnificativ) — de aici popularitatea practică.
Greșeala tipică de simulare: după prima partiționare, elevii cred că vectorul e „aproape sortat”. Fals — garantat e doar că pivotul e pe poziția finală și că cele două zone sunt corect separate față de el; în interiorul zonelor ordinea poate fi oricare.
MergeSort și interclasarea
Interclasarea este operația de bază: din două șiruri deja sortate, se construiește un singur șir sortat, comparând mereu primele elemente rămase din fiecare și copiindu-l pe cel mai mic. Costul este liniar, O(m + n), iar la examen apare și de sine stătător (probleme cu două fișiere sau doi vectori sortați).
MergeSort aplică Divide et Impera pe schema inversă lui QuickSort:
- împarte vectorul în două jumătăți (fără nicio comparație de valori — tăietura e la mijloc);
- sortează recursiv fiecare jumătate;
- interclasează cele două jumătăți sortate — aici se face toată munca de comparare.
Proprietăți de reținut, în oglindă cu QuickSort:
- complexitate O(n log n) în toate cazurile — inclusiv cel defavorabil; vectorul de intrare nu influențează numărul de niveluri de înjumătățire;
- cere memorie suplimentară O(n) pentru interclasare — nu sortează pe loc;
- este stabilă (elementele egale își păstrează ordinea relativă), spre deosebire de QuickSort și de selecție.
Întrebarea-capcană standard: „la QuickSort munca se face la împărțire (partiționare), la MergeSort la combinare (interclasare)” — adevărat, și exact invers formulările false din distractori. Cine reține unde muncește fiecare algoritm rezolvă grila din prima.
Căutarea binară
Căutarea binară găsește o valoare într-un vector obligatoriu sortat, înjumătățind la fiecare pas intervalul de căutare:
- se compară valoarea căutată x cu elementul din mijlocul intervalului curent;
- dacă sunt egale, căutarea se oprește cu succes;
- dacă x e mai mic, căutarea continuă în jumătatea stângă; dacă e mai mare, în jumătatea dreaptă;
- când intervalul devine vid, valoarea nu există în vector.
Complexitatea este O(log n): la fiecare comparație, intervalul se înjumătățește, deci numărul maxim de pași este aproximativ log₂(n) + 1. Pentru n = 1.000.000, ajung circa 20 de comparații — comparativ cu până la 1.000.000 la căutarea secvențială; acest contrast numeric e cerut frecvent.
Condiția de aplicare, subliniată pentru că aici pică cei mai mulți: vectorul trebuie să fie sortat. Pe un vector nesortat, algoritmul rulează fără eroare, dar poate rata valori existente — rezultatul e pur și simplu greșit, nu doar lent. Dacă vectorul nu e sortat și se fac multe căutări, merită sortat o dată (O(n log n)) și apoi căutat binar; pentru o singură căutare, secvențiala O(n) e mai ieftină decât sortare + binară.
Detaliu de implementare punctat la BAC: mijlocul se calculează cu `m = (st + dr) / 2`, iar actualizările corecte sunt `st = m + 1`, respectiv `dr = m - 1`; păstrarea lui m în interval (`st = m`) poate produce buclă infinită.
Analiza complexității: cum compari algoritmii
Complexitatea timp a unui algoritm exprimă modul în care numărul de operații crește odată cu dimensiunea datelor de intrare n, în notația O: se păstrează termenul dominant și se ignoră constantele. Ierarhia care trebuie știută pe de rost, de la cel mai rapid:
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)
Reguli practice de estimare direct din cod:
- o buclă simplă de la 1 la n → O(n); două bucle imbricate până la n → O(n²); două bucle succesive → tot O(n), nu O(n²) — confuzia imbricat/succesiv e cea mai frecventă greșeală de analiză;
- o buclă în care variabila se înjumătățește (sau se dublează) până atinge n → O(log n);
- algoritmii Divide et Impera cu înjumătățire și lucru liniar pe nivel → O(n log n).
Tabelul sortărilor, cerut ca atare:
- selecție, inserție, bule: O(n²) (inserția are cazul favorabil O(n));
- QuickSort: O(n log n) mediu, O(n²) defavorabil;
- MergeSort: O(n log n) garantat, memorie O(n);
- numărare: O(n + k), doar pentru valori întregi din interval mic.
De reținut și limita teoretică: nicio sortare bazată pe comparații nu poate fi mai rapidă decât O(n log n) în cazul general — counting sort o depășește doar pentru că nu compară elemente.
De reținut
- sortare prin selecție
- sortare O(n²) care la fiecare pas i caută minimul zonei nesortate și îl interschimbă cu elementul de pe poziția i; după pasul i, primele i+1 elemente sunt definitiv pe pozițiile finale
- sortare prin inserție
- sortare O(n²) care inserează fiecare element la locul potrivit în prefixul deja sortat; pe un vector aproape sortat atinge cazul favorabil O(n)
- sortare prin numărare
- sortare fără comparații, O(n + k), care numără aparițiile fiecărei valori într-un vector de frecvență; aplicabilă doar valorilor întregi dintr-un interval cunoscut și mic
- QuickSort
- sortare Divide et Impera care partiționează vectorul în jurul unui pivot adus pe poziția sa finală, apoi sortează recursiv cele două zone; O(n log n) în medie, O(n²) în cazul defavorabil
- MergeSort
- sortare Divide et Impera care împarte vectorul în două jumătăți, le sortează recursiv și le interclasează; O(n log n) în toate cazurile, cu memorie suplimentară O(n)
- interclasare
- construirea unui șir sortat din două șiruri deja sortate, prin compararea repetată a primelor elemente rămase; cost liniar O(m + n)
- căutare binară
- căutare într-un vector sortat prin înjumătățirea repetată a intervalului, comparând valoarea căutată cu elementul din mijloc; complexitate O(log n)
- notația O
- exprimarea ordinului de creștere al numărului de operații în funcție de dimensiunea datelor, păstrând termenul dominant și ignorând constantele
- algoritm stabil de sortare
- algoritm care păstrează ordinea relativă a elementelor egale; MergeSort este stabil, QuickSort și selecția nu sunt
Greșeli frecvente
Greșit: Căutarea binară s-ar putea aplica pe orice vector, cel mult ar fi mai lentă pe unul nesortat
Corect: Pe un vector nesortat, căutarea binară dă rezultate greșite (poate rata valori existente), nu doar lente — sortarea prealabilă este condiție de corectitudine, nu de viteză
Greșit: QuickSort ar fi O(n log n) în orice situație, doar e sortarea „rapidă”
Corect: QuickSort are cazul defavorabil O(n²) — tipic pe vector deja sortat cu pivot ales la capăt; garanția O(n log n) în toate cazurile o oferă MergeSort
Greșit: După pasul i al sortării prin inserție, primele i+1 elemente ar fi pe pozițiile lor finale
Corect: La inserție prefixul e sortat, dar provizoriu — elemente ulterioare mai mici pot intra în el; pozițiile finale după fiecare pas sunt garantate la sortarea prin selecție
Greșit: Două bucle care apar una după alta în program ar da complexitate O(n²)
Corect: Buclele succesive se adună: O(n) + O(n) = O(n); doar buclele imbricate se înmulțesc și dau O(n²)
Greșit: Sortarea prin numărare ar fi universal mai bună, fiind liniară
Corect: Counting sort cere valori întregi dintr-un interval mic și cunoscut și memorie O(k); pentru valori reale sau intervale uriașe este inaplicabilă, iar sortările prin comparații rămân singura opțiune
Test — 6 întrebări ca la examen
1. Vectorul (9, 3, 7, 1) se sortează crescător prin selecție. Cum arată vectorul după primul pas (prima interschimbare)?
- (3, 9, 7, 1)
- (1, 3, 7, 9)
- (1, 3, 9, 7)
- (3, 7, 1, 9)
Vezi răspunsul
(1, 3, 9, 7). Selecția caută minimul întregului vector (1, aflat pe ultima poziție) și îl interschimbă cu primul element: 9 și 1 își schimbă locurile, rezultând (1, 3, 9, 7). Varianta (3, 9, 7, 1) descrie o interschimbare de vecini — primul pas din bubble sort, confuzia clasică între cele două metode.
2. Care sortare are complexitate O(n log n) garantată în toate cazurile, inclusiv cel defavorabil?
- QuickSort
- sortarea prin inserție
- MergeSort
- sortarea prin selecție
Vezi răspunsul
MergeSort. MergeSort înjumătățește mereu vectorul indiferent de valorile lui, deci are log n niveluri cu lucru liniar pe fiecare — O(n log n) garantat. QuickSort e distractorul puternic: e O(n log n) doar în medie, iar în cazul defavorabil (pivot prost pe vector sortat) degradează la O(n²).
3. Într-un vector sortat cu 1024 de elemente se caută binar o valoare care nu există în vector. Numărul de comparații efectuate este aproximativ:
- 1024
- 512
- 100
- 10
Vezi răspunsul
10. Intervalul se înjumătățește la fiecare pas: 1024 → 512 → … → 1, adică log₂(1024) = 10 pași până la epuizarea intervalului. Varianta 512 e capcana pentru cine crede că binara „taie vectorul în două o singură dată”; 1024 ar fi căutarea secvențială completă.
4. După prima partiționare din QuickSort se poate garanta că:
- vectorul este aproape sortat
- pivotul se află pe poziția sa finală din vectorul sortat
- prima jumătate a vectorului este sortată
- minimul și maximul se află pe pozițiile extreme
Vezi răspunsul
pivotul se află pe poziția sa finală din vectorul sortat. Partiționarea așază pivotul exact pe poziția lui finală, cu elementele mai mici la stânga și mai mari la dreapta — dar în interiorul celor două zone ordinea e arbitrară, deci nimic nu e „aproape sortat” sau complet sortat. Celelalte variante promit garanții pe zone pe care partiționarea nu le atinge.
5. Un vector conține un milion de numere naturale, fiecare cel mult egal cu 100. Cea mai eficientă sortare pentru acest caz este:
- sortarea prin numărare, cu un vector de frecvență de 101 elemente
- QuickSort, pentru că este cea mai rapidă sortare generală
- sortarea prin inserție, pentru că vectorul are valori mici
- căutarea binară aplicată repetat
Vezi răspunsul
sortarea prin numărare, cu un vector de frecvență de 101 elemente. Valori întregi într-un interval mic și cunoscut — condițiile ideale pentru counting sort, care rulează în O(n + k) = O(n), sub limita O(n log n) a oricărei sortări prin comparații, deci și a lui QuickSort. Inserția confundă valorile mici cu vectorul aproape sortat, iar căutarea binară nici măcar nu e o metodă de sortare.
6. Un program conține o buclă de la 1 la n, urmată (nu imbricată) de două bucle imbricate, fiecare de la 1 la n. Complexitatea totală este:
- O(n³)
- O(n²)
- O(n log n)
- O(n)
Vezi răspunsul
O(n²). Buclele succesive se adună: O(n) + O(n²) = O(n²), pentru că termenul dominant absoarbe restul. O(n³) e capcana pentru cine înmulțește toate cele trei bucle ca și cum ar fi imbricate — doar ultimele două sunt una în interiorul celeilalte.