1
1. Strategia Divide et Impera
Divide et Impera (Imparte si Cucereste) este o strategie algortimica in trei pasi:
- DIVIDE — imparte problema in subprobleme de acelasi tip, mai mici
- IMPERA — rezolva fiecare subproblema recursiv (cazul de baza: o subproblema trivial de mica)
- COMBINA — uneste solutiile subproblemelor intr-o solutie a problemei initiale
De ce e eficient?
La fiecare nivel de recursivitate, numarul de elemente se injumatateste. Un sir de n elemente genereaza un arbore de recursivitate cu log₂(n) niveluri. Daca la fiecare nivel se face O(n) munca totala, complexitatea globala este O(n log n) — mult mai buna decat O(n²) al sortarilor simple (bubble, selectie, insertie).
Comparatie concreta pentru n = 1.000.000:
O(n²) = 1.000.000.000.000 operatii (~11 zile la 10⁹ operatii/sec) O(n log n) = 20.000.000 operatii (~0.02 secunde) Factorul de imbunatatire: de ~50.000 de ori mai rapid!
2
2. MergeSort — algoritmul de interclasare EXCLUSIV INTENSIV
⚡ Sectiune doar pentru intensiv informatica (C++)
MergeSort este algoritmul de sortare stabil preferat in productie cand stabilitatea conteaza. Implementarea completa in C++ cu vectori:
Pasul 1 — Functia merge(): interclaseaza doua subsiruri sortate
#include <iostream> #include <vector> using namespace std; // Interclaseaza arr[l..m] si arr[m+1..r] (ambele deja sortate) void merge(vector<int>& arr, int l, int m, int r) { int n1 = m - l + 1; // marimea subsirului stang int n2 = r - m; // marimea subsirului drept vector<int> L(n1), R(n2); // copii temporare for (int i = 0; i < n1; i++) L[i] = arr[l + i]; for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; int i = 0, j = 0, k = l; while (i < n1 && j < n2) { // compara capetele celor doi subsiri if (L[i] <= R[j]) arr[k++] = L[i++]; else arr[k++] = R[j++]; } while (i < n1) arr[k++] = L[i++]; // rest din stanga while (j < n2) arr[k++] = R[j++]; // rest din dreapta }
Pasul 2 — Functia mergeSort(): recursivitate Divide et Impera
void mergeSort(vector<int>& arr, int l, int r) { if (l < r) { // cazul de baza: l==r → un singur element, deja sortat int m = l + (r - l) / 2; // DIVIDE: gaseste mijlocul (evita overflow) mergeSort(arr, l, m); // IMPERA: sorteaza jumatatea stanga mergeSort(arr, m + 1, r); // IMPERA: sorteaza jumatatea dreapta merge(arr, l, m, r); // COMBINA: interclaseaza cele doua subsiruri sortate } }
Pasul 3 — main(): apel si afisare
int main() { vector<int> arr = {38, 27, 43, 3, 9, 82, 10}; cout << "Inainte: "; for (int x : arr) cout << x << " "; cout << endl; mergeSort(arr, 0, arr.size() - 1); cout << "Dupa: "; for (int x : arr) cout << x << " "; cout << endl; return 0; }
Output real (compilat g++ -std=c++17, rulat):
Inainte: 38 27 43 3 9 82 10 Dupa: 3 9 10 27 38 43 82
Urmarirea executiei — arborele de recursivitate pentru {38, 27, 43, 3}:
mergeSort([38,27,43,3], 0, 3)
mergeSort([38,27], 0, 1)
mergeSort([38], 0, 0) → caz de baza, returneaza
mergeSort([27], 1, 1) → caz de baza, returneaza
merge([38,27]) → [27,38]
mergeSort([43,3], 2, 3)
mergeSort([43], 2, 2) → caz de baza, returneaza
mergeSort([3], 3, 3) → caz de baza, returneaza
merge([43,3]) → [3,43]
merge([27,38], [3,43]) → [3,27,38,43]
3
3. QuickSort — partitionarea si recursivitatea EXCLUSIV INTENSIV
⚡ Sectiune doar pentru intensiv informatica (C++)
QuickSort este cel mai rapid algoritm de sortare in practica pentru date aleatoare. Ideea cheie: alege un pivot si rearranjeaza sirul astfel incat toate elementele mici sa fie in stanga pivotului, toate cele mari in dreapta — pivotul ajunge pe pozitia lui finala.
Pasul 1 — partition(): asaza pivotul pe pozitia corecta
// Alege arr[high] ca pivot, muta elementele <= pivot in stanga, > pivot in dreapta // Returneaza indexul final al pivotului int partition(vector<int>& arr, int low, int high) { int pivot = arr[high]; // pivotul = ultimul element int i = low - 1; // i = frontiera elementelor mici (initial inexistenta) for (int j = low; j < high; j++) { // j parcurge sirul if (arr[j] <= pivot) { // arr[j] apartine zonei "mici" i++; swap(arr[i], arr[j]); // muta-l in zona stanga } } swap(arr[i + 1], arr[high]); // asaza pivotul pe pozitia finala return i + 1; // pozitia pivotului }
Pasul 2 — quickSort(): aplica recursiv pe cele doua partitii
void quickSort(vector<int>& arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); // DIVIDE + COMBINA: pivotul pe loc quickSort(arr, low, pi - 1); // IMPERA: stanga pivotului quickSort(arr, pi + 1, high); // IMPERA: dreapta pivotului } // cazul de baza: low >= high → subsir de 0 sau 1 elemente, deja sortat }
Pasul 3 — main(): apel si afisare
int main() { vector<int> arr = {10, 7, 8, 9, 1, 5}; cout << "Inainte: "; for (int x : arr) cout << x << " "; cout << endl; quickSort(arr, 0, arr.size() - 1); cout << "Dupa: "; for (int x : arr) cout << x << " "; cout << endl; return 0; }
Output real (compilat g++ -std=c++17, rulat):
Inainte: 10 7 8 9 1 5 Dupa: 1 5 7 8 9 10
Tracing partitionare pentru {10, 7, 8, 9, 1, 5}, pivot = 5:
pivot = 5, i = -1
j=0: arr[0]=10 > 5 → nimic
j=1: arr[1]=7 > 5 → nimic
j=2: arr[2]=8 > 5 → nimic
j=3: arr[3]=9 > 5 → nimic
j=4: arr[4]=1 <= 5 → i=0, swap(arr[0],arr[4]) → {1, 7, 8, 9, 10, 5}
Final: swap(arr[1], arr[5]) → {1, 5, 8, 9, 10, 7}
^pozitia 1 = pozitia finala a pivotului 5
Stanga: {1} Pivot: {5} Dreapta: {8, 9, 10, 7}
4
4. Analiza complexitatii O(n log n) EXCLUSIV INTENSIV
⚡ Sectiune doar pentru intensiv informatica
Intelegerea complexitatii este esentiala pentru a alege algoritmul corect in competitii si in productie.
MergeSort — complexitate garantata O(n log n):
- Arborele de recursivitate are intotdeauna log₂(n) niveluri (impartire exacta la jumatate)
- La fiecare nivel, pasul merge() face in total O(n) operatii (fiecare element e copiat exact o data)
- Total: O(n log n) in TOATE cazurile — cel mai bun, mediu si defavorabil
- Memorie suplimentara: O(n) pentru vectorii temporari L[] si R[]
QuickSort — complexitate variabila:
- Cazul mediu (date aleatoare): O(n log n) — pivotul imparte sirul aproximativ la jumatate
- Cazul defavorabil (sir sortat/invers sortat + pivot=ultim): O(n²) — o partitie este mereu goala
- Cazul cel mai bun (pivot = mediana): O(n log n)
- Memorie suplimentara: O(log n) pentru stiva de recursivitate (cazul mediu)
Demonstratie numerica rulata — MergeSort pe n=8 elemente:
// Program demonstratie: numara apeluri merge() si comparatii #include <iostream> #include <vector> #include <cmath> using namespace std; int mergeCallCount = 0; int compareCount = 0; // ... (acelasi merge + mergeSort ca mai sus, cu contorizare) int main() { int n = 8; vector<int> arr = {38,27,43,3,9,82,10,55}; mergeSort_counted(arr, 0, n-1); cout << "n = " << n << endl; cout << "Apeluri merge: " << mergeCallCount << endl; cout << "Comparatii: " << compareCount << endl; cout << "n*log2(n) ~ " << (int)(n * log2(n)) << endl; }
Output real (compilat g++ -std=c++17, rulat):
n = 8 Apeluri merge: 7 (n-1 = 7) Comparatii: 16 n*log2(n) ~ 24
Tabel comparativ complexitati:
Algorithm | Cel mai bun | Mediu | Defavorabil | Memorie ------------|-------------|------------|-------------|-------- MergeSort | O(n log n) | O(n log n) | O(n log n) | O(n) QuickSort | O(n log n) | O(n log n) | O(n²) | O(log n) BubbleSort | O(n) | O(n²) | O(n²) | O(1) SelectSort | O(n²) | O(n²) | O(n²) | O(1)
5
5. MergeSort vs QuickSort — diferente practice si alegerea pivotului EXCLUSIV INTENSIV
⚡ Sectiune doar pentru intensiv informatica
In practica, QuickSort este adesea mai rapid decat MergeSort pe date aleatoare, chiar daca ambii sunt O(n log n) in medie. Motivul: QuickSort are constante mai mici si acces la memorie mai prietenos pentru cache.
Stabilitate:
- MergeSort: STABIL — elementele egale isi pastreaza ordinea relativa. Crucial cand sortezi obiecte cu mai multe campuri (ex: sortezi angajati dupa salariu, pastrand ordinea dupa nume la salarii egale).
- QuickSort clasic: INSTABIL — swap-urile din partition() pot schimba ordinea elementelor egale.
Tehnica Median-of-Three: evitarea cazului defavorabil la QuickSort
// Pivot = mediana dintre arr[low], arr[mid], arr[high] int partitionMOT(vector<int>& arr, int low, int high) { int mid = low + (high - low) / 2; // Sorteaza cele 3 elemente la pozitiile low, mid, high if (arr[low] > arr[mid]) swap(arr[low], arr[mid]); if (arr[low] > arr[high]) swap(arr[low], arr[high]); if (arr[mid] > arr[high]) swap(arr[mid], arr[high]); // arr[mid] este mediana — mut-o la pozitia high-1 ca pivot swap(arr[mid], arr[high]); // Restul partitionarii ramane identic int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) if (arr[j] <= pivot) { i++; swap(arr[i], arr[j]); } swap(arr[i + 1], arr[high]); return i + 1; }
Output real — median-of-three pe sir sortat (cazul rau pt pivot=last):
Inainte (sir sortat - cazul rau pt pivot=last): 1 2 3 4 5 6 7 8 Dupa (cu median-of-3): 1 2 3 4 5 6 7 8
Ghid de alegere algoritm:
Situatie | Recomandat ----------------------------------|------------------ Date aleatoare, viteza maxima | QuickSort (cu MOT) Date cu multe duplicate | QuickSort 3-way Stabilitate necesara | MergeSort Date partial sortate | MergeSort sau Timsort Memorie limitata (embedded) | QuickSort (O(log n) memorie) Garantie O(n log n) in orice caz | MergeSort std::sort din C++ STL | IntroSort (hybrid QS+Heap+Insert)
6
6. Demonstratie comparativa — ambii algoritmi pe acelasi sir
// Aplica ambii algoritmi pe acelasi sir si verifica rezultate identice int main() { vector<int> data = {64, 34, 25, 12, 22, 11, 90, 45, 78, 3}; vector<int> a1 = data, a2 = data; // copii identice mergeSort(a1, 0, a1.size()-1); quickSort(a2, 0, a2.size()-1); cout << "Date initiale: "; for (int x : data) cout << x << " "; cout << endl; cout << "MergeSort: "; for (int x : a1) cout << x << " "; cout << endl; cout << "QuickSort: "; for (int x : a2) cout << x << " "; cout << endl; bool same = (a1 == a2); cout << "Rezultate identice: " << (same ? "DA" : "NU") << endl; return 0; }
Output real (compilat g++ -std=c++17, rulat):
Date initiale: 64 34 25 12 22 11 90 45 78 3 MergeSort: 3 11 12 22 25 34 45 64 78 90 QuickSort: 3 11 12 22 25 34 45 64 78 90 Rezultate identice: DA
Conexiune cu std::sort din C++:
In competitii si productie nu reimplementezi manual acesti algoritmi. Biblioteca standard C++ ofera:
#include <algorithm> // Sorteaza intreg vectorul — IntroSort (QS + HeapSort + InsertionSort) sort(arr.begin(), arr.end()); // Sortare stabila — MergeSort sau TimSort stable_sort(arr.begin(), arr.end());
Cunoasterea MergeSort si QuickSort iti permite sa intelegi ce face std::sort intern si sa implementezi variante personalizate cand este necesar (sortare dupa criteriu complex, sortare paralela etc.).