Modul 08 — Metode de sortare · Clasa a IX-a Fable

Sortarea prin selecția minimului

La fiecare pas: caută cel mai mic element din zona nesortată și interschimbă-l cu primul element al ei. Repetă până totul e verde.

linia galbenă = instrucțiunea care tocmai s-a executat

trecere: 0

comparări: 0

interschimbări: 0

v =

nesortat scanare (j) minimul curent sortat definitiv

Apasă „Pas" — algoritmul caută minimul din zona nesortată. 👆

🎯 pbInfo #509 — Ordonare — sortează un vector crescător ↗

De reținut: după trecerea i, primele i+1 poziții sunt DEFINITIV sortate — nu se mai ating. Numărul de comparări e mereu același: n(n−1)/2, indiferent cum arată vectorul.

Sortarea cu listă de frecvențe

Când valorile sunt într-un interval mic și cunoscut (note 1–10, cifre 0–9): construiești f[] (Modulul 07!), apoi recompui vectorul scriind fiecare valoare de f[v] ori. Zero comparări.

note =

Apasă „Pas" — faza 1 numără, faza 2 rescrie sortat. 👆

🎯 pbInfo #264 — MaxCif — cifra cea mai frecventă, cu vector de frecvență ↗

Limita metodei: merge doar când valorile sunt puține și cunoscute dinainte. Pentru numere până la un miliard, f[] n-ar încăpea în memorie — acolo rămân selecția/bulele/sort().

Metoda bulelor (bubble sort)

Compari mereu doi vecini; dacă-s în ordine greșită, îi interschimbi. La fiecare trecere, cel mai mare „urcă" la suprafață ca o bulă. Dacă o trecere nu face nicio interschimbare — gata, e sortat!

linia galbenă = instrucțiunea care tocmai s-a executat

trecere: 0

comparări: 0

interschimbări: 0

v =

nesortat pereche comparată interschimbare! sortat definitiv

Apasă „Pas" — perechile vecine se compară pe rând. 👆

🎯 pbInfo #618 — Inaltimi — sortare care ține minte poziția inițială ↗

Detaliul care aduce puncte: varianta cu semaforul „sortat" se oprește devreme pe vectori aproape ordonați. Încearcă v = 1 2 3 4 5 și numără comparările!

Cursa: selecția minimului vs. bulele

Ambele au ~n²/2 comparări în cel mai rău caz. Diferența apare pe vectori „prietenoși" — testează toate scenariile!

n =

Selecția minimului

—

comparări (mereu n(n−1)/2 — nu „vede" ordinea)

Bulele (cu oprire devreme)

—

comparări

alege un scenariu 👆

🎯 pbInfo #390 — ordonare — aceeași sarcină, dar cu sort() din bibliotecă ↗

Concluzia pentru BAC: selecția minimului face PUȚINE interschimbări (max n−1) dar mereu toate comparările; bulele fac multe interschimbări, dar pot termina în O(n) pe un vector deja sortat. Niciuna nu scapă de O(n²) în cazul general.

Notația Big-O — de la zero

Ai văzut că selecția face mereu multe comparări, iar bulele se pot opri devreme. Dar cum PUNEM cifre pe „mult" și „puțin"? Cu Big-O. O luăm de la capăt.

Pasul zero: ce numărăm?

Un calculator face pași simpli: o adunare, o comparație, un acces la v[i] — fiecare durează cam la fel, aproape instantaneu. Big-O nu măsoară SECUNDE (depind de calculator), ci câți pași faci când datele cresc. Notăm cu n mărimea datelor (câte elemente are vectorul) și numărăm cum crește munca odată cu n.

O(1) — constant

›x = v[0] + v[n-1];

→ 1 pas, mereu

Nu contează dacă n = 10 sau n = 1.000.000 — accesul direct la o poziție e la fel de rapid. Timp CONSTANT.

O(n) — liniar

›for (i = 0; i < n; i++)

› s += v[i];

→ n pași (bucla rulează de n ori)

Un for peste tot vectorul = n pași. Dublezi n → dublezi timpul. Aici stau suma, minimul, frecvențele.

O(n²) — pătratic

›for (i = 0; i < n; i++)

› for (j = 0; j < n; j++)

› ...

→ n · n = n² pași

Buclă ÎN buclă: pentru fiecare din cei n, încă n pași. Dublezi n → de 4 ori mai mult timp! Aici stau selecția și bulele.

O(log n) — logaritmic

›while (n > 0)

› n = n / 2;

→ ~log₂ n pași

La fiecare pas ÎNJUMĂTĂȚEȘTI. n = 1000 → doar ~10 pași! Aici stă Euclid cu împărțiri (M03), iar la anul căutarea binară.

Regula de aur: ignori constantele și termenii mici — contează doar termenul care CREȘTE cel mai repede. O(2n + 5) = O(n) · O(n² + n) = O(n²). La n mare, restul devine praf.

Vezi cum crește — grafic și tabel, legate de ACELAȘI cursor

n = 16 sau scrie exact:

cât de departe privim:

O(1) constant O(log n) O(n) liniar O(n·log n) O(n²) pătratic

De ce scară logaritmică pe verticală? Pe o scară normală, O(n²) ar strivi toate celelalte linii la podea (nu s-ar vedea nimic). Aici fiecare treaptă în sus = ×10 operații — așa încap TOATE cele 5 curbe, clar separate. Punctul din grafic = exact rândul din tabel.

Complexitate	Exemplu	operații la n ales	creștere

Concept-cheie: la n = 1000, O(n²) ar face 1.000.000 de operații, O(n·log n) doar ~10.000 — de o sută de ori mai puțin. Alegerea algoritmului contează enorm, mult mai mult decât „optimizările" mărunte.

Fișa de sinteză

Sortările, la pachet.

Selecția minimului: caută minimul zonei nesortate → swap pe prima poziție liberă; n(n−1)/2 comparări mereu.

Bulele: compară vecini + semaforul „sortat" pentru oprire devreme; O(n) pe vector deja ordonat.

Frecvențe: f[v[i]]++ apoi recompui — zero comparări, dar doar pe valori mici și cunoscute.

Big-O: O(1) < O(log n) < O(√n) < O(n) < O(n·log n) < O(n²) — ierarhia de știut pe de rost.

În practică: sort(v, v+n) din <algorithm> (O(n·log n)) — dar la BAC se cere să LE ȘTII de mână!

În clasa a X-a: pe vectorii sortați construiești căutarea binară și interclasarea — de-asta contează sortarea.

🎯 Acum exersează pe pbinfo.ro.
Intră la Probleme → Categorii și lucrează pe categoria „Metode de sortare" — acolo găsești zeci de probleme, de la ordonarea simplă până la sortări care trebuie să țină minte poziția inițială. Pentru sortarea cu listă de frecvențe, caută în categoria „Tablouri unidimensionale (vectori)".

Regula casei: primele 5–6 probleme le scrii de mână (selecție sau bule). Abia după aceea ai voie sort() — la BAC ți se cere metoda, nu rezultatul.

Cele patru probleme legate mai sus (#509, #264, #618, #390) sunt doar începutul — în categorie mai ai zeci.

Punem ordine în date