1
1. Sortarea prin selectie
Idee: La fiecare pas i, cauta minimul din subsirul nesortat (pozitiile i..n-1) si plaseaza-l pe pozitia i prin interschimbare. Dupa pasul i, primele i+1 pozitii sunt sortate definitiv.
Urmarire pas cu pas pe [64, 25, 12, 22, 11]:
Start: [64, 25, 12, 22, 11] Pasul 1: [11, 25, 12, 22, 64] (minim=11, schimba poz 0 cu poz 4) Pasul 2: [11, 12, 25, 22, 64] (minim=12, schimba poz 1 cu poz 2) Pasul 3: [11, 12, 22, 25, 64] (minim=22, schimba poz 2 cu poz 3) Pasul 4: [11, 12, 22, 25, 64] (minim=25, deja pe loc)
Implementare Python (output verificat):
def selectie(v): n = len(v) for i in range(n - 1): min_idx = i for j in range(i + 1, n): if v[j] < v[min_idx]: min_idx = j v[i], v[min_idx] = v[min_idx], v[i] # interschimbare return v lista = [64, 25, 12, 22, 11] print("Inainte:", lista) selectie(lista) print("Dupa: ", lista)
Output real (rulat cu python):
Inainte: [64, 25, 12, 22, 11] Dupa: [11, 12, 22, 25, 64]
Complexitate: O(n²) - bucla exterioara face n-1 pasi, bucla interioara face n-1-i comparatii la pasul i. Total comparatii: n(n-1)/2. Numarul de interschimbari este cel mult n-1 (avantaj fata de bule).
2
2. Sortarea cu lista de frecvente
Idee: In loc sa comparam si sa mutam elemente, numaram de cate ori apare fiecare valoare intr-un tablou auxiliar freq. Apoi parcurgem freq de la 0 la val_max si reconstituim lista sortata: scriem valoarea k de freq[k] ori. Conditie: functioneaza doar pentru numere intregi nonnegative cu domeniu cunoscut si rezonabil de mic.
Pas cu pas pe [3, 1, 4, 1, 5]:
Lista initiala: [3, 1, 4, 1, 5] val_max = 5 Pasul 1 - construire freq: freq = [0, 0, 0, 0, 0, 0] (indici 0..5) citim 3 -> freq[3]++ -> freq = [0, 0, 0, 1, 0, 0] citim 1 -> freq[1]++ -> freq = [0, 1, 0, 1, 0, 0] citim 4 -> freq[4]++ -> freq = [0, 1, 0, 1, 1, 0] citim 1 -> freq[1]++ -> freq = [0, 2, 0, 1, 1, 0] citim 5 -> freq[5]++ -> freq = [0, 2, 0, 1, 1, 1] Pasul 2 - reconstituire lista sortata: val=0: freq[0]=0 -> nimic val=1: freq[1]=2 -> scriem 1, 1 val=2: freq[2]=0 -> nimic val=3: freq[3]=1 -> scriem 3 val=4: freq[4]=1 -> scriem 4 val=5: freq[5]=1 -> scriem 5 Rezultat: [1, 1, 3, 4, 5]
Implementare Python (output verificat):
def sortare_frecvente(v): if not v: return [] val_max = max(v) freq = [0] * (val_max + 1) # tablou de frecvente for x in v: freq[x] += 1 # numara aparitiile rezultat = [] for val in range(val_max + 1): rezultat.extend([val] * freq[val]) # adauga val de freq[val] ori return rezultat lista = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3] print("Inainte:", lista) print("Dupa: ", sortare_frecvente(lista))
Output real (rulat cu python):
Inainte: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3] Dupa: [1, 1, 2, 3, 3, 4, 5, 5, 6, 9]
Complexitate: O(n + val_max) - parcurgere lista O(n) + parcurgere freq O(val_max). Daca val_max este proportional cu n, algoritmul devine O(n) - mai rapid decat O(n²)! Limitari: necesita memorie extra O(val_max); nu functioneaza pentru numere reale, negative sau cu domeniu foarte mare.
3
3. Sortarea prin metoda bulelor (Bubble Sort)
Idee: La fiecare runda, parcurge lista de la stanga la dreapta si schimba fiecare pereche de vecini aflati in ordine gresita. Dupa runda i, cele mai mari i elemente sunt plasate corect la sfarsit.
Urmarire runde pe [5, 3, 8, 4, 2]:
Start: [5, 3, 8, 4, 2] Runda 1: [3, 5, 4, 2, 8] (8 a urcat la pozitia finala) Runda 2: [3, 4, 2, 5, 8] (5 a ajuns pe loc) Runda 3: [3, 2, 4, 5, 8] Runda 4: [2, 3, 4, 5, 8] (sortat)
Implementare Python (output verificat):
def bule(v): n = len(v) for i in range(n - 1): for j in range(n - 1 - i): if v[j] > v[j + 1]: v[j], v[j + 1] = v[j + 1], v[j] return v lista = [64, 34, 25, 12, 22, 11, 90] print("Inainte:", lista) bule(lista) print("Dupa: ", lista)
Output real (rulat cu python):
Inainte: [64, 34, 25, 12, 22, 11, 90] Dupa: [11, 12, 22, 25, 34, 64, 90]
Complexitate: O(n²) in cazul mediu si cel mai defavorabil. Numarul de comparatii = n(n-1)/2. Numarul de interschimbari poate fi pana la n(n-1)/2. Cazul cel mai bun: cu o optimizare care detecteaza lista deja sortata (flag), complexitatea devine O(n).
4
4. Sortarea prin insertie BONUS - extra-programa
⚠ Algoritm extra-programa
Sortarea prin insertie nu este prevazuta in programa oficiala (nici OMEN 4.350/2025, nici OMECI 5099/2009 nu o numesc explicit). Este inclusa ca bonus pentru aprofundare, datorita proprietatii utile de complexitate O(n) pe liste aproape sortate. Nu este materie de examen standard.
Idee: Considera ca la pasul i, subsirul v[0..i-1] este deja sortat. Ia elementul v[i] (cheia) si insereaza-l la pozitia corecta in subsirul sortat, deplasand elementele mai mari spre dreapta.
Urmarire pas cu pas pe [5, 2, 8, 1, 9]:
Start: [5, 2, 8, 1, 9] Pasul 1: [2, 5, 8, 1, 9] (inserat 2 - a trecut de 5) Pasul 2: [2, 5, 8, 1, 9] (inserat 8 - deja la loc) Pasul 3: [1, 2, 5, 8, 9] (inserat 1 - a trecut de 8, 5, 2) Pasul 4: [1, 2, 5, 8, 9] (inserat 9 - deja la loc)
Implementare Python (output verificat):
def insertie(v): n = len(v) for i in range(1, n): cheie = v[i] # elementul de inserat j = i - 1 while j >= 0 and v[j] > cheie: v[j + 1] = v[j] # deplaseaza spre dreapta j -= 1 v[j + 1] = cheie # plaseaza cheia return v lista = [12, 11, 13, 5, 6] print("Inainte:", lista) insertie(lista) print("Dupa: ", lista)
Output real (rulat cu python):
Inainte: [12, 11, 13, 5, 6] Dupa: [5, 6, 11, 12, 13]
Complexitate: O(n²) in cazul mediu si defavorabil. Cazul cel mai bun: O(n) - daca lista e deja sortata, while-ul nu se executa niciodata, facand exact n-1 comparatii. Insertia este preferata pentru liste aproape sortate.
5
5. Comparatie algoritmi
Algoritmii clasici O(n²) difera in detalii importante. Lista de frecvente are complexitate mai buna dar cu restrictii.
Tabel comparativ:
Algoritm | Complexitate | Interschimbari | Restrictii -----------------|-----------------|-----------------|--------------------------- Selectie | O(n^2) | cel mult n-1 | nicio restrictie Lista frecvente | O(n + val_max) | 0 (tablou aux) | doar int nonneg, dom. mic Bule | O(n^2) | pana la n(n-1)/2| nicio restrictie Insertie (bonus) | O(n^2) / O(n)* | pana la n(n-1)/2| nicio restrictie *O(n) doar cand lista este aproape sortata
Numar de comparatii worst case O(n^2), n(n-1)/2:
n=5: 10 comparatii n=10: 45 comparatii n=100: 4950 comparatii n=1000: 499500 comparatii
Concluzii practice:
- Selectia face putine interschimbari - avantajos cand mutarea de date e costisitoare
- Lista de frecvente e liniara cand domeniul valorilor e mic si cunoscut
- Bule e usor de inteles si explicat, utila pedagogic
- Pentru n mare se folosesc QuickSort sau MergeSort cu O(n log n)
6
6. Implementare C++ EXCLUSIV INTENSIV
⚡ Sectiune doar pentru intensiv informatica
In C++ sortam tablouri unidimensionale (int v[]). Diferente fata de Python: tipuri explicite, indici cu [], interschimbare cu variabila temporara. Toate implementarile de mai jos au fost compilate si rulate cu g++ -std=c++17.
Selectie in C++:
#include <iostream> using namespace std; int main() { int v[] = {64, 25, 12, 22, 11}; int n = 5; for (int i = 0; i < n - 1; i++) { int min_idx = i; for (int j = i + 1; j < n; j++) if (v[j] < v[min_idx]) min_idx = j; int tmp = v[i]; v[i] = v[min_idx]; v[min_idx] = tmp; } cout << "Sortat: "; for (int i = 0; i < n; i++) cout << v[i] << " "; cout << endl; return 0; }
Output real (compilat g++ -std=c++17, rulat):
Sortat: 11 12 22 25 64
Lista de frecvente in C++:
#include <iostream> using namespace std; int main() { int v[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3}; int n = 10, val_max = 9; int freq[10] = {}; // initializat cu 0 for (int i = 0; i < n; i++) freq[v[i]]++; cout << "Sortat: "; for (int k = 0; k <= val_max; k++) for (int t = 0; t < freq[k]; t++) cout << k << " "; cout << endl; return 0; }
Output real (compilat g++ -std=c++17, rulat):
Sortat: 1 1 2 3 3 4 5 5 6 9
Bule in C++:
#include <iostream> using namespace std; int main() { int v[] = {64, 34, 25, 12, 22, 11, 90}; int n = 7; for (int i = 0; i < n - 1; i++) for (int j = 0; j < n - 1 - i; j++) if (v[j] > v[j + 1]) { int tmp = v[j]; v[j] = v[j+1]; v[j+1] = tmp; } cout << "Sortat: "; for (int i = 0; i < n; i++) cout << v[i] << " "; cout << endl; return 0; }
Output real (compilat g++ -std=c++17, rulat):
Sortat: 11 12 22 25 34 64 90
7
7. Urmarirea executiei - exercitii tip BAC
La BAC, un exercitiu tipic cere sa trasezi executia unui algoritm de sortare pas cu pas sau sa identifici ce algoritm s-a folosit dupa o secventa de stari intermediare.
Exercitiu rezolvat: Sortare prin selectie pe [29, 10, 14, 37, 13]
Start: [29, 10, 14, 37, 13]
Pas i=0: minim=10 la poz 1; schimba v[0] cu v[1]
-> [10, 29, 14, 37, 13]
Pas i=1: minim=13 la poz 4; schimba v[1] cu v[4]
-> [10, 13, 14, 37, 29]
Pas i=2: minim=14 la poz 2; deja pe loc
-> [10, 13, 14, 37, 29]
Pas i=3: minim=29 la poz 4; schimba v[3] cu v[4]
-> [10, 13, 14, 29, 37]
Rezultat final: [10, 13, 14, 29, 37]
Cum recunosti algoritmul dupa starile intermediare:
Selectie: la fiecare pas exact o pozitie din stanga se fixeaza definitiv
-> front care avanseaza stanga spre dreapta
Bule: la fiecare runda maximul ramas ajunge la sfarsit
-> front care avanseaza dreapta spre stanga
Lista frecvente: nu exista stari intermediare vizibile - produce direct lista
sortata (nu se poate urma pas cu pas ca celelalte)
Tehnica de urmarire la BAC:
- Identifica n (lungimea listei) si algoritmul cerut
- Aplica algoritmul pas cu pas, scriind starea dupa fiecare iteratie exterioara
- Verifica: dupa n-1 pasi/runde, lista trebuie sa fie sortata complet