Modul 09 — 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.

v =

nesortat scanare (j) minimul curent sortat definitiv

trecere: 0

comparări: 0

interschimbări: 0

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

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 08!), apoi recompui vectorul scriind fiecare valoare de f[v] ori. Zero comparări.

note =

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

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!

v =

nesortat pereche comparată interschimbare! sortat definitiv

trecere: 0

comparări: 0

interschimbări: 0

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

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 👆

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 ← trage cursorul; graficul, punctele și tabelul se mișcă împreună

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.

Exersează pe pbinfo.ro:

#509 · ușoară

Ordonare

Ordonați crescător un vector — implementează selecția sau bulele, de mână.

Rezolvă pe pbinfo.ro →

#618 · medie

Inaltimi

Afișați numerele de ordine ale copiilor în ordinea înălțimii — sortare care ține minte poziția inițială.

Rezolvă pe pbinfo.ro →

#390 · medie

ordonare

Sortați un vector crescător — de data asta cu sort() din bibliotecă, pentru comparație.

Rezolvă pe pbinfo.ro →

#264 · ușoară

MaxCif

Cifra cea mai frecventă — vectorul de frecvențe în acțiune (M08 + M09).

Rezolvă pe pbinfo.ro →