clasa a XI-a · Metode de programare · lecția 5
Metoda Divide et Impera: MergeSort, QuickSort, căutare binară recursivă
60 minintensiv / recomandat și la neintensiv (apare indirect la recursivitate)
Înainte de lecția asta: XI.4 Recursivitate (2): pe vectori, pe șiruri și algoritmul de umplere (fill)
Ce vei ști după lecție
- Înțelegi cei trei pași: împarte, rezolvă subproblemele, combină.
- Scrii funcții divide et impera pe vectori (sumă, maxim, verificări).
- Implementezi căutarea binară recursivă și MergeSort.
- Cunoști ideea QuickSort și problema Turnurilor din Hanoi.
Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓
Clasa a XI-aLecția 5 din 21 · mai sunt 16Urmează: XI.6 · Backtracking (1): principiul metodei și generarea permutărilorVezi toate lecțiile
Cuprins
- Ideea: împarte, rezolvă, combină
- Căutarea binară, recursiv
- MergeSort: sortarea prin interclasare
- QuickSort (ideea)
- Turnurile din Hanoi
- Greșeli frecvente
- La BAC
- Exersează pe hârtie
- Mai departe (pentru cine vrea mai mult)
- Rezumat
- Fișa de lucru
- Probleme de lucru
- Temă
- Pentru cei care vor mai mult
- Grile din subiectele de BAC
- Citește și exersează în plus
- Răspunsuri
Fișiere PDF și de lucru
- Lecția în PDF
versiunea de printat
- Fișa de lucru: Divide et impera: căutare binară, MergeSort, QuickSort, Hanoi
5 pagini · 90 min
1. Ideea: împarte, rezolvă, combină
Ai de verificat 1000 de lucrări. Dacă le dai în două grămezi unor colegi, iar ei fac la fel mai departe, la final fiecare are doar câteva lucrări, iar tu doar aduni rezultatele. Aceasta este metoda Divide et Impera (lat. „împarte și stăpânește”):
- Divide: împarte problema în două (sau mai multe) subprobleme de același tip, mai mici;
- Impera: rezolvă subproblemele recursiv, până la cazuri banale (un singur element);
- Combină: din soluțiile subproblemelor obții soluția întregii probleme.
Pe un vector a[st..dr] împărțim la mijloc: mij = (st + dr) / 2, adică a[st..mij] și a[mij+1..dr].
#include <iostream>
using namespace std;
int a[101], n, apeluri;
int suma(int st, int dr)
{
apeluri++; // numărăm apelurile
if (st == dr) return a[st]; // un singur element: banal
int mij = (st + dr) / 2;
int s1 = suma(st, mij); // subproblema din stânga
int s2 = suma(mij + 1, dr); // subproblema din dreapta
return s1 + s2; // combinare
}
int maxim(int st, int dr)
{
if (st == dr) return a[st];
int mij = (st + dr) / 2;
int m1 = maxim(st, mij), m2 = maxim(mij + 1, dr);
return m1 > m2 ? m1 : m2;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cout << suma(1, n) << ' ' << maxim(1, n) << ' ' << apeluri;
return 0;
}De ce așa?
De ce atâtea apeluri (2n − 1), dacă o buclă ar face doar n adunări? Pentru suma și maximul metoda D&I nu câștigă nimic: tot n operații se fac. Rostul acestor exemple este să înțelegi structura. Câștigul real apare când combinarea e ieftină și problema se împarte bine (căutare binară, sortare), cum vedem mai jos.
La BAC
Grilă frecventă: „De câte ori se apelează funcția pentru un vector cu n elemente?” Pentru împărțirea în două până la un element, numărul de apeluri este 2n − 1 (n frunze + n − 1 împărțiri). Desenează arborele pentru n = 5 și verifică: 9 apeluri.
Intrare / ieșire
| Intrare | Ieșire |
|---|---|
61 2 3 4 5 6 |
21 6 11 (suma, maximul, apelurile) |
17 |
7 7 1 |
2. Căutarea binară, recursiv
Aici „combinarea” lipsește: rezolvăm doar una dintre jumătăți, fiindcă vectorul este sortat și știm în care se află x.
#include <iostream>
using namespace std;
int a[101], n;
bool caut(int st, int dr, int x)
{
if (st > dr) return false; // interval vid: nu există
int mij = (st + dr) / 2;
if (a[mij] == x) return true;
if (x < a[mij]) return caut(st, mij - 1, x);
return caut(mij + 1, dr, x);
}
int main()
{
int x;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> x;
cout << (caut(1, n, x) ? "DA" : "NU");
return 0;
}Urmărire pentru x = 12, a = (2, 4, 6, 8, 10, 12, 14):
| apel | st | dr | mij | a[mij] | decizie |
|---|---|---|---|---|---|
caut(1, 7, 12) |
1 | 7 | 4 | 8 | 12 > 8: dreapta |
caut(5, 7, 12) |
5 | 7 | 6 | 12 | găsit: true |
3. MergeSort: sortarea prin interclasare
Sortăm cele două jumătăți, apoi le interclasăm (ca la lecția X.5): luăm mereu cel mai mic dintre primele elemente ale celor două părți sortate.
#include <iostream>
using namespace std;
int a[100001], aux[100001], n;
void mergeSort(int st, int dr)
{
if (st >= dr) return; // 0 sau 1 element: deja sortat
int mij = (st + dr) / 2;
mergeSort(st, mij);
mergeSort(mij + 1, dr);
int i = st, j = mij + 1, k = 0; // interclasare în aux
while (i <= mij && j <= dr)
if (a[i] <= a[j]) aux[++k] = a[i++];
else aux[++k] = a[j++];
while (i <= mij) aux[++k] = a[i++];
while (j <= dr) aux[++k] = a[j++];
for (int t = 1; t <= k; t++) a[st + t - 1] = aux[t]; // copiem înapoi
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
mergeSort(1, n);
for (int i = 1; i <= n; i++) cout << a[i] << ' ';
return 0;
}De ce așa?
De ce <= în if (a[i] <= a[j])? La elemente egale luăm întâi pe cel din stânga: sortarea rămâne stabilă (elementele egale își păstrează ordinea inițială). De ce vectorul aux? Interclasarea nu se poate face pe loc fără să strici elemente încă necitite; scriem rezultatul în aux și îl copiem înapoi. De ce O(n log n)? Vectorul se împarte de log₂ n ori (adâncimea arborelui), iar la fiecare nivel interclasările parcurg în total n elemente. Pentru 10⁶ elemente sunt ~2·10⁷ pași, față de 10¹² la bule.
Urmărire pentru mergeSort(1, 6) pe (5, 2, 9, 1, 7, 3):
| apel | partea sortată după apel |
|---|---|
mergeSort(1, 3) |
2 5 9 |
mergeSort(4, 6) |
1 3 7 |
| interclasare (1, 3) cu (4, 6) | 1 2 3 5 7 9 |
Intrare / ieșire
| Intrare | Ieșire |
|---|---|
65 2 9 1 7 3 |
1 2 3 5 7 9 |
31 1 1 |
1 1 1 |
4. QuickSort (ideea)
Alegem un pivot; mutăm spre stânga elementele mai mici decât el și spre dreapta pe cele mai mari (partiționare), apoi sortăm recursiv cele două părți. Aici nu mai e nevoie de combinare: după partiționare, fiecare parte se sortează pe loc.
#include <iostream>
using namespace std;
int a[100001], n;
void quickSort(int st, int dr)
{
int i = st, j = dr, pivot = a[(st + dr) / 2];
while (i <= j)
{
while (a[i] < pivot) i++; // primul element care NU e mai mic decât pivotul
while (a[j] > pivot) j--; // primul (de la dreapta) care NU e mai mare
if (i <= j) { swap(a[i], a[j]); i++; j--; }
}
if (st < j) quickSort(st, j);
if (i < dr) quickSort(i, dr);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
quickSort(1, n);
for (int i = 1; i <= n; i++) cout << a[i] << ' ';
return 0;
}De ce așa?
De ce pivotul din mijloc? Dacă ai alege mereu primul element, un vector deja sortat ar da părți de n − 1 și 0 elemente: O(n²). Pivotul din mijloc se comportă bine pe vectori sortați sau aproape sortați. Pe date „rău intenționate” se alege un pivot aleator. În practică, sort() din STL (<algorithm>) folosește o variantă îmbunătățită a acestei idei (introsort); la Bac poți folosi sort.
| MergeSort | QuickSort | |
|---|---|---|
| timp (în medie) | O(n log n) | O(n log n) |
| cel mai rău caz | O(n log n) | O(n²) (rar) |
| memorie în plus | O(n) (aux) |
O(log n) (stiva) |
| stabil | da | nu |
5. Turnurile din Hanoi
Mutăm n discuri de pe tija A pe C, folosind B, mutând un singur disc o dată și nepunând niciodată un disc mare peste unul mic. Gândește recursiv: pentru a muta cel mai mare disc, trebuie ca celelalte n − 1 să fie deja pe tija de ajutor.
- mutăm
n − 1discuri de pe A pe B (folosind C); - mutăm discul cel mare de pe A pe C;
- mutăm cele
n − 1discuri de pe B pe C (folosind A).
#include <iostream>
using namespace std;
void hanoi(int n, char a, char b, char c) // mută n discuri de pe a pe c, folosind b
{
if (n == 0) return;
hanoi(n - 1, a, c, b); // n-1 discuri: a -> b (ajutor: c)
cout << a << "->" << c << '\n'; // discul cel mare: a -> c
hanoi(n - 1, b, a, c); // n-1 discuri: b -> c (ajutor: a)
}
int main()
{
int n;
cin >> n;
hanoi(n, 'A', 'B', 'C');
return 0;
}De ce așa?
De ce se inversează rolurile tijelor în apeluri? În primul apel scopul este tija B, iar C devine „ajutorul”; în al doilea, sursa este B și ajutorul este A. Parametrii (a, b, c) sunt roluri (sursă, ajutor, destinație), nu tije fixe. Numărul de mutări M(n) = 2·M(n − 1) + 1, deci 2ⁿ − 1.
Intrare / ieșire
| Intrare | Ieșire |
|---|---|
1 |
A->C |
2 |
A->BA->CB->C |
6. Greșeli frecvente
| Greșeala | Efect | Corect |
|---|---|---|
mij = (st + dr) / 2 cu st, dr mari și int |
depășire la valori foarte mari | st + (dr - st) / 2 |
subintervale care se suprapun (st..mij și mij..dr) |
se numără mij de două ori |
st..mij și mij+1..dr |
lipsește cazul de bază (st == dr) |
recursie infinită | verifică-l primul |
| căutare binară pe vector nesortat | rezultat greșit | sortează întâi |
aux nu se copiază înapoi în a |
vectorul rămâne nesortat | for … a[st + t - 1] = aux[t] |
QuickSort cu < și > greșite (<=) |
buclă infinită la elemente egale | < și > stricte |
7. La BAC
La BAC
La Subiectul I apar subprograme D&I cu st, dr, mij pe un vector dat: „ce valoare întoarce apelul?” sau „de câte ori se apelează?”. Metoda: desenezi arborele de apeluri cu intervalele [st, dr] și completezi de jos în sus. Numărul de apeluri la împărțire în două până la un element: 2n − 1.
8. Exersează pe hârtie
Răspunsurile sunt la final: încearcă întâi singur.
1. Desenează arborele de apeluri pentru suma(1, 6). Câte apeluri sunt?
2. Câte apeluri face suma pentru n = 5? Dar pentru n = 8?
3. Scrie o funcție divide et impera care numără elementele pare dintr-un vector a[st..dr].
4. Câte mutări face hanoi(5, …)? Dacă o mutare durează o secundă, cât durează pentru 64 de discuri?
5. Pentru a = (2, 4, 6, 8, 10, 12, 14), scrie apelurile caut(1, 7, 4).
6. Interclasează (2, 5, 9) cu (1, 3, 7). Câte comparații se fac între elemente?
7. De ce căutarea binară are nevoie de vector sortat?
8. Estimează numărul de operații pentru MergeSort cu n = 10⁶ (≈ n·log₂ n) și compară cu bulele (≈ n²/2).
9. Cum se comportă QuickSort cu pivotul a[st] pe un vector deja sortat?
10. (BAC) Ce afișează?
int f(int st, int dr, int v[]) { if (st == dr) return v[st]; int mij = (st + dr) / 2; return f(st, mij, v) + f(mij + 1, dr, v); }
// v = (7, 1, 2, 5, 4) indexat de la 1: cout << f(1, 5, v);9. Mai departe (pentru cine vrea mai mult)
Numărarea inversiunilor. Câte perechi (i, j) cu i < j și a[i] > a[j] are un vector? Soluția naivă e O(n²); cu MergeSort se poate în O(n log n): când la interclasare luăm un element din dreapta, el este mai mic decât toate elementele rămase în stânga, deci adăugăm mij − i + 1 inversiuni.
#include <iostream>
using namespace std;
int a[100001], aux[100001], n;
long long inv;
void ms(int st, int dr)
{
if (st >= dr) return;
int mij = (st + dr) / 2;
ms(st, mij); ms(mij + 1, dr);
int i = st, j = mij + 1, k = 0;
while (i <= mij && j <= dr)
if (a[i] <= a[j]) aux[++k] = a[i++];
else { inv += mij - i + 1; aux[++k] = a[j++]; } // a[j] e mai mic decât a[i..mij]
while (i <= mij) aux[++k] = a[i++];
while (j <= dr) aux[++k] = a[j++];
for (int t = 1; t <= k; t++) a[st + t - 1] = aux[t];
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
ms(1, n);
cout << inv;
return 0;
}Teorema master (ideea). Dacă o problemă se împarte în 2 subprobleme de mărime n/2 și combinarea costă O(n), timpul este T(n) = 2T(n/2) + O(n) = O(n log n). La căutarea binară: T(n) = T(n/2) + O(1) = O(log n).
Alte aplicații. Înmulțirea rapidă a numerelor mari (Karatsuba), cele mai apropiate două puncte din plan, transformata Fourier rapidă (FFT), căutarea celei de-a k-a valori (quickselect).
Rezumat
- Împarte (
mij), rezolvă recursiv, combină; cazul de bază: un element. - Căutare binară: doar o jumătate. MergeSort: ambele jumătăți + interclasare. QuickSort: partiționare, apoi ambele părți.
- Împărțire în două până la un element:
2n − 1apeluri. - MergeSort: O(n log n), stabil, memorie în plus; QuickSort: O(n log n) în medie.
- Hanoi:
2ⁿ − 1mutări.
Fișa de lucru
Ai citit lecția? Printează fișa sau deschide-o pe ecran și rezolvă exercițiile în ordine.
Fișă de lucru · 5 pagini · 90 min
Divide et impera: căutare binară, MergeSort, QuickSort, Hanoi
- Desenezi arborele de apeluri pe intervale [st, dr] și spui ce întoarce, ce afișează și de câte ori se apelează o funcție D&I.
- Urmărești de mână căutarea binară, interclasările din MergeSort, partiționarea din QuickSort și mutările de la Hanoi.
- Scrii funcții D&I în care pasul de combinare este partea care contează.
Te-ai blocat la un exercițiu?
Probleme de lucru
Începe cu acestea, în ordine. Problemele se deschid pe pbinfo.ro, unde trimiți soluția și primești punctajul.
- ușoară
sumvec#1015
https://www.pbinfo.ro/probleme/1015/sumvec
- ușoară
maxim6#1019
https://www.pbinfo.ro/probleme/1019/maxim6
- medie
cautarebinara#1155
https://www.pbinfo.ro/probleme/1155/cautarebinara
Temă
Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.
- ușoară
sumparevec#1017
https://www.pbinfo.ro/probleme/1017/sumparevec
- ușoară
cntimpare#1018
https://www.pbinfo.ro/probleme/1018/cntimpare
- ușoară
cmmdc3#1023
https://www.pbinfo.ro/probleme/1023/cmmdc3
- ușoară
https://www.pbinfo.ro/probleme/1152/verificareordonatdivimp
- ușoară
hanoi#2527
https://www.pbinfo.ro/probleme/2527/hanoi
- medie
mergesort#1025
https://www.pbinfo.ro/probleme/1025/mergesort
Pentru cei care vor mai mult
- medie
quicksort#1024
https://www.pbinfo.ro/probleme/1024/quicksort
- medie
nrinversiuni#3206
https://www.pbinfo.ro/probleme/3206/nrinversiuni
Grile din subiectele de BAC
Exerciții de tip grilă din variantele de Bacalaureat. Se rezolvă pe pbinfo.ro, care îți verifică imediat răspunsul.
- #1013tablou v cu 8 valori date; subprogram recursiv pe st..dr: ce se obține
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=1013
- #1014tablou a cu 9 valori date; subprogram divide et impera: ce se obține
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=1014
- #1616algoritm în pseudocod cu vector, s și d: secvența de ...
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=1616
- #1617f recursiv pe tabloul (7, 1, 2, 5, 4): valoarea apelului
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=1617
- #1708câte inversiuni conține vectorul A = [5, 3, 2, 4, 1]
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=1708
- #1350f(st, dr, v[]) recursiv: valoarea întoarsă pe un vector dat
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=1350
Citește și exersează în plus
- Metoda Divide et Impera · pbinfo.ro
https://www.pbinfo.ro/articole/7651/divide-et-impera
- Sortarea prin interclasare – MergeSort · pbinfo.ro
https://www.pbinfo.ro/articole/7667/sortarea-prin-interclasare
- Sortarea rapidă – QuickSort · pbinfo.ro
https://www.pbinfo.ro/articole/7666/quicksort
- VisuAlgo — Sorting (MergeSort, QuickSort) · visualgo.net
animații pas cu pas pentru ambele sortări, cu exemplele tale
https://visualgo.net/en/sorting
- Turnurile din Hanoi (joc online) · mathsisfun.com
încearcă singur cu 3, 4, 5 discuri și numără mutările
https://www.mathsisfun.com/games/towerofhanoi.html
- CSES — Sorting and Searching · cses.fi
secțiunea „Sorting and Searching”: probleme cu căutare binară și sortări (engleză)
https://cses.fi/problemset/list/
Te-ai blocat la lecția asta?
Scrie-mi ce nu iese și vedem împreună de unde se blochează.
Răspunsuri
Exersează pe hârtie
1. Rădăcina [1, 6] → [1, 3] și [4, 6]; [1, 3] → [1, 2] și [3, 3]; [1, 2] → [1, 1] și [2, 2]; [4, 6] → [4, 5] și [6, 6]; [4, 5] → [4, 4] și [5, 5]. Total 11 apeluri (6 frunze + 5 împărțiri), conform formulei 2·6 − 1.
2. 2·5 − 1 = 9 apeluri; 2·8 − 1 = 15.
3.
#include <iostream>
using namespace std;
int a[101], n;
int nrPare(int st, int dr)
{
if (st == dr) return a[st] % 2 == 0; // un singur element: 1 dacă e par, altfel 0
int mij = (st + dr) / 2;
return nrPare(st, mij) + nrPare(mij + 1, dr);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cout << nrPare(1, n);
return 0;
}4. 2⁵ − 1 = 31 de mutări. Pentru 64 de discuri: 2⁶⁴ − 1 ≈ 1,8·10¹⁹ secunde ≈ 585 de miliarde de ani.
5. caut(1, 7, 4): mij = 4, a[4] = 8, 4 < 8 → caut(1, 3, 4): mij = 2, a[2] = 4 → găsit (true). Două apeluri.
6. Rezultat 1 2 3 5 7 9. Comparații: (2, 1) → 1; (2, 3) → 2; (5, 3) → 3; (5, 7) → 5; (9, 7) → 7; apoi partea din dreapta s-a terminat și se copiază restul din stânga (9) fără comparații. Total 5 comparații.
7. Decizia „stânga sau dreapta?” se bazează pe x < a[mij]: dacă vectorul nu e sortat, x poate fi în ambele părți și jumătatea eliminată ar putea conține elementul căutat.
8. MergeSort: ≈ 10⁶ · 20 = 2·10⁷ operații (milisecunde). Bule: ≈ 10¹² / 2 = 5·10¹¹ operații (minute-ore).
9. Pe un vector sortat, pivotul a[st] este cel mai mic element: o parte are 0 elemente, cealaltă n − 1. Adâncimea recursiei devine n și timpul O(n²), cu risc de stack overflow. Pivotul din mijloc evită cazul acesta.
10. 19: funcția adună toate elementele (7 + 1 + 2 + 5 + 4 = 19), chiar dacă împarte vectorul în două la fiecare pas.