Divide et impera (probleme clasice: sortare, minim/maxim, k-th element)

Divide et impera („dezbină și stăpânește”) este o tehnică fundamentală de programare bazată pe recursivitate. Ea constă în trei pași: 1) Divide: problema inițială este împărțită în două sau mai multe subprobleme mai mici, de același tip. 2) Impera: fiecare subproblemă se rezolvă recursiv (sau direct, când devine trivială).

3) Combină: soluțiile subproblemelor se combină pentru a obține soluția problemei inițiale. Pentru sortare, algoritmul MergeSort divide vectorul în două jumătăți, sortează fiecare jumătate recursiv și apoi le interclasează (merge) în timp O(n). QuickSort alege un pivot, partiționează vectorul în elemente mai mici și mai mari decât pivotul, apoi sortează recursiv fiecare parte.

Găsirea minimului și maximului se poate face prin împărțirea vectorului în perechi, comparând recursiv și păstrând valorile extreme; complexitatea este O(n) cu mai puține comparații decât varianta secvențială. Problema k-th element (selecția) cere găsirea celui de-al k-lea cel mai mic element. O soluție eficientă este algoritmul QuickSelect: se alege un pivot, se partiționează, apoi se decide recursiv în care parte se află al k-lea element.

În caz mediu, complexitatea este O(n), iar în cazul cel mai defavorabil O(n^2). Se poate ameliora alegând pivotul prin metoda „median of medians” pentru O(n) garantat. Tehnica divide et impera este esențială pentru Bacalaureat și pentru optimizarea algoritmilor, având aplicații în sortări, căutări, parcurgeri de arbori, înmulțire rapidă a matricelor și multe altele.

Exemple

• Exemplul 1: Găsirea minimului și maximului dintr-un vector. Vector: [5, 2, 9, 1, 7, 3]. Algoritmul împarte recursiv în [5,2,9] și [1,7,3]. Pentru prima jumătate: max=9, min=2. Pentru a doua: max=7, min=1. Comparând, obținem min=1, max=9. Rezultat corect.
• Exemplul 2: Sortare prin MergeSort. Vector: [4, 1, 3, 2]. Se împarte în [4,1] și [3,2]. Se sortează: [1,4] și [2,3]. Se interclasează: comparăm 1 cu 2 → 1; 4 cu 2 → 2; 4 cu 3 → 3; rămâne 4 → [1,2,3,4].
• Exemplul 3: K-th element (selecție). Vector: [10, 4, 5, 8, 6, 11, 26], k=3 (al 3-lea cel mai mic). Alegem pivot=8 (după partiționare: [4,5,6] <8, [10,11,26] >8. Partea stângă are 3 elemente, deci al 3-lea cel mai mic este ultimul din stânga: 6. Corect.

Concepte cheie: Divide et impera: împarte, rezolvă recursiv, combină, MergeSort: sortare stabilă, O(n log n) garantat, QuickSort: sortare în loc, pivot și partiționare, O(n^2) în caz prost, Selecția k-th element (QuickSelect): găsește al k-lea cel mai mic element, O(n) mediu, Algoritm minim/maxim recursiv: reduce numărul de comparații la ~3n/2