Exemple clasice — Merge Sort și prietenii

De ce contează?

Ai o singură unealtă în mână — „împarte și cucerește” — și în fața ta trei probleme care par să nu aibă nimic în comun: să sortezi un teanc de cărți de joc, să cauți un cuvânt în dicționar, să ridici un număr la o putere uriașă. Surprinzător, aceeași mișcare le rezolvă pe toate: rupi problema în jumătăți, te ocupi separat de fiecare, apoi lipești rezultatele la loc. În lecția asta vezi cum cei trei pași — împarte, rezolvă, combină — apar, identici, în trei algoritmi clasici.

Merge Sort: cei 3 pași

Merge Sort sortează un șir aplicând fix tiparul divide et impera:

Împarte șirul la mijloc în două jumătăți.
Rezolvă sortând recursiv fiecare jumătate (subprobleme mai mici).
Combină interclasând cele două jumătăți sortate într-un singur șir sortat.

Cazul de bază: o secvență cu un singur element este deja sortată — nu o mai împarți.

Hai să urmărim pe [5, 2, 8, 1]. Întâi cobori, împărțind la mijloc:

[5, 2, 8, 1] se rupe în [5, 2] și [8, 1]
[5, 2] se rupe în [5] și [2]
[8, 1] se rupe în [8] și [1]

Acum urci, interclasând perechile sortate:

[5] cu [2] dă [2, 5]
[8] cu [1] dă [1, 8]
[2, 5] cu [1, 8] dă [1, 2, 5, 8]

sortat

Rezultatul final dupa ce toate interclasarile urca inapoi: [1 2 5 8].

Observă: toată „inteligența” stă în pasul de combinare. Împărțirea e banală (mijlocul), iar la întoarcere doi indici parcurg cele două jumătăți și aleg mereu elementul mai mic.

Implementare C++

#include <iostream>
using namespace std;

const int MAXN = 1000;
int aux[MAXN]; // vector auxiliar pentru interclasare

// combina a[st..mid] si a[mid+1..dr], ambele deja sortate
void merge(int a[], int st, int mid, int dr) {
    int i = st, j = mid + 1, k = st;
    while (i <= mid && j <= dr) {
        if (a[i] <= a[j]) aux[k++] = a[i++];
        else aux[k++] = a[j++];
    }
    while (i <= mid) aux[k++] = a[i++]; // ce a ramas in stanga
    while (j <= dr) aux[k++] = a[j++];  // ce a ramas in dreapta
    for (int t = st; t <= dr; t++) a[t] = aux[t]; // copiaza inapoi
}

void mergeSort(int a[], int st, int dr) {
    if (st >= dr) return;              // caz de baza: 0 sau 1 element
    int mid = st + (dr - st) / 2;      // imparte: mijlocul
    mergeSort(a, st, mid);             // rezolva: jumatatea stanga
    mergeSort(a, mid + 1, dr);         // rezolva: jumatatea dreapta
    merge(a, st, mid, dr);             // combina: interclasare
}

int main() {
    int a[] = {5, 2, 8, 1};
    int n = 4;
    mergeSort(a, 0, n - 1);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << "\n"; // 1 2 5 8
    return 0;
}

Cele trei rânduri din mergeSort sunt exact cei trei pași: mid împarte, cele două apeluri rezolvă, merge combină.

Alte exemple pe scurt

Căutare binară — divide et impera unde combinarea e trivială. Împarți șirul sortat la mijloc, dar nu rezolvi ambele jumătăți: arunci una întreagă și continui doar în cea care poate conține valoarea. Nu mai e nimic de lipit la întoarcere, de unde și viteza.

int cautareBinara(int a[], int st, int dr, int target) {
    if (st > dr) return -1;            // caz de baza: interval gol
    int mid = st + (dr - st) / 2;      // imparte la mijloc
    if (a[mid] == target) return mid;
    if (a[mid] < target)
        return cautareBinara(a, mid + 1, dr, target); // doar dreapta
    return cautareBinara(a, st, mid - 1, target);     // doar stanga
}

Exponentiere rapidă — calculezi a^n folosind a^(n/2). Dacă știi p = a^(n/2), atunci a^n = p * p pentru n par, respectiv a^n = p * p * a pentru n impar. Cheia: calculezi a^(n/2) o singură dată și îl ridici la pătrat.

long long putere(long long a, int n) {
    if (n == 0) return 1;             // caz de baza: a^0 = 1
    long long p = putere(a, n / 2);   // rezolva o data subproblema
    if (n % 2 == 0) return p * p;     // combina: p ridicat la patrat
    return p * p * a;                 // n impar: mai inmultim cu a
}

Complexitate

Algoritm	Timp	De ce
Merge Sort	O(n log n)	log n niveluri, fiecare interclasează în total n elemente
Căutare binară	O(log n)	un singur subapel pe nivel, log n niveluri
Exponentiere rapidă	O(log n)	`n` se înjumătățește la fiecare apel

Diferența vine din câte subprobleme rezolvi și cât costă combinarea: Merge Sort rezolvă ambele jumătăți și combină în O(n); celelalte două coboară pe un singur drum.

Observația-cheie

Toți trei algoritmii au exact aceeași structură în trei pași — împarte, rezolvă recursiv, combină. Ce îi deosebește nu e tiparul, ci câte subprobleme ataci (una sau două) și cât de scumpă e combinarea (trivială la căutare binară, O(n) la Merge Sort). Recunoaște tiparul o dată și îl vei vedea în zeci de probleme.

Greșeli frecvente

Interclasare fără vector auxiliar corect: încerci să muți elementele direct în șir și suprascrii valori încă necitite. Folosește un aux separat, apoi copiază înapoi.
Exponentiere cu apel dublu: scrii putere(a, n/2) * putere(a, n/2) în loc să salvezi rezultatul într-o variabilă. Faci doi arbori de apeluri identici și complexitatea redevine O(n) — pierzi tot avantajul lui log n.
mid cu overflow: scrii (st + dr) / 2; la indici mari suma depășește int. Folosește mid = st + (dr - st) / 2.
Caz de bază lipsă: uiți if (st >= dr) return; la Merge Sort sau if (n == 0) return 1; la exponentiere. Recursia nu se mai oprește și apare stack overflow.

Vizualizare

Urmărește cum șirul se rupe în jumătăți tot mai mici și cum, la întoarcere, interclasarea le reasamblează sortate.

Indiciu

Concentrează-te pe săgețile de la întoarcere: acolo, în pasul de combinare, se face sortarea propriu-zisă. Coborârea doar pregătește terenul.

Recapitulare

Merge Sort sortează în O(n log n) prin cei trei pași: împarte la mijloc, sortează recursiv jumătățile, interclasează cu un vector auxiliar.
Căutarea binară și exponentierea rapidă folosesc același tipar, dar coboară pe un singur drum (combinare trivială) — de aceea sunt O(log n).
Recunoști un algoritm divide et impera după structura în trei pași; valoarea reală stă aproape mereu în pasul de combinare.