Divide et impera este o tehnica de elaborare a algoritmilor care constă în:

1. Descompunerea cazului ce trebuie rezolvat într-un număr de subcazuri mai mici

ale aceleiaşi probleme.
2. Rezolvarea succesivă şi independentă a fiecăruia din aceste subcazuri.
3. Recompunerea subsoluţiilor astfel obţinute pentru a găsi soluţia cazului
iniţial.
Algoritmul formal al metodei divide et impera:
funcţion divimp(x)
{returnează o soluţie pentru cazul x}
if x este suficient de mic then return adhoc(x)
{descompune x în subcazurile x1, x2, …, xk}
for i ← 1 to k do yi ← divimp(xi)
{recompune y1, y2, …, yk în scopul obţinerii soluţiei y pentru x}
return y
unde adhoc este subalgoritmul de bază folosit pentru rezolvarea micilor subcazuri
ale problemei în cauză

Mergesort (sortarea prin interclasare)

Fie T[1 .. n] un tablou pe care dorim sa-l sortam crescător. Prin tehnica divide et
impera putem
proceda astfel: separăm tabloul T în două părţi de mărimi cât mai apropiate, sortăm
aceste părţi prin
apeluri recursive, apoi interclasăm soluţiile pentru fiecare parte, fiind atenţi să
păstrăm ordonarea
crescătoare a elementelor. Obţinem următorul algoritm:
procedure mergesort(T[1 .. n])
{sortează în ordine crescătoare tabloul T}
if n este mic
then insert(T)
else arrays U[1 .. n div 2], V[1 .. (n+1) div 2]
U ← T[1 .. n div 2]
V ← T[1 + (n div 2) .. n]
mergesort(U); mergesort(V)
merge(T, U, V)

Mergesort a l'algorithme de pseudocode suivant :

procedure mergesort (T[1 .. n])
{trier le tableau T par ordre croissant}
if n est petit
then insérez (T)
else tableaux U[1 .. n div 2], V[1 .. (n+1) div 2]
U ← T[1 .. n div 2]
V ← T[1 + (n div 2) .. n]
mergesort(U); mergesort(V)
merge(T, U, V)

Spaţiul de memorie necesar pentru tablourile auxiliare U şi V este în (n). Mai

precis, pentru a sorta
un tablou de n = 2^k elemente, presupunând că descompunerea este totală, acest
spaţiu este de 2n

Quicksort (sortarea rapida)

Algoritmul de sortare quicksort, se bazează de asemenea pe principiul divide et
impera. Spre deosebire de mergesort, partea nerecursivă a algoritmului este
dedicata construirii subcazurilor şi nu combinării soluţiilor lor.
Ca prim pas, algoritmul alege un element pivot din tabloul care trebuie sortat.
Tabloul este apoi
partiţionat în două subtablouri, alcătuite de-o parte şi de alta a acestui pivot în
următorul mod: elementele mai mari decât pivotul sunt mutate în dreapta pivotului,
iar celelalte elemente sunt mutate în stânga pivotului. Acest mod de partiţionare
este numit pivotare. În continuare, cele două subtablouri sunt sortate în mod
independent prin apeluri recursive ale algoritmului. Rezultatul este tabloul
complet sortat; nu mai este necesară nici o interclasare. Pentru a echilibra
mărimea celor două subtablouri care se obţin la fiecare partiţionare, ar fi ideal
să alegem ca pivot elementul median. Intuitiv, mediana unui tablou T este elementul
m din T, astfel încât numărul elementelor din T mai mici decât m este egal cu
numărul celor
mai mari decât m. Din păcate, găsirea medianei necesita mai mult timp decât merită.
De aceea, putem pur
şi simplu să folosim ca pivot primul element al tabloului.

Iată cum arată acest algoritm:

procedure quicksort(T[i .. j])
{sortează în ordine crescătoare tabloul T[i .. j]}
if j−i este mic
then insert(T[i .. j])
else pivot(T[i .. j], l)
{după pivotare, avem:
i <= k < l → T[k] <= T[l]
l < k <= j → T[k] > T[l]}
quicksort(T[i .. l−1])
quicksort(T[l+1 .. j])

Mai rămâne să concepem un algoritm de pivotare cu timp liniar, care să parcurgă

tabloul T o
singură dată. Putem folosi următoarea tehnica de pivotare: parcurgem tabloul T o
singură dată, pornind
însă din ambele capete. Încercaţi să înţelegeţi cum funcţionează acest algoritm de
pivotare, în care
p = T[i] este elementul pivot:
procedure pivot(T[i .. j], l)
{permută elementele din T[i .. j] astfel încât, în final,
elementele lui T[i .. l−1] sunt  p,
T[l] = p,
iar elementele lui T[l+1 .. j] sunt > p}
p ← T[i]
k ← i; l ← j+1
repeat k ← k+1 until T[k] > p or k >= j
repeat l ← l−1 until T[l] <= p
while k < l do
interschimbă T[k] şi T[l]
repeat k ← k+1 until T[k] > p
repeat l ← l−1 until T[l] <= p
{pivotul este mutat în poziţia lui finală}
interschimbă T[i] şi T[l]

Best-case and average-case time complexity: O(n log n). In the best-case scenario,
the pivot chosen consistently divides the array into roughly equal halves. Worst-
case time complexity: O(n^2). In the worst-case scenario, the pivot is always
chosen in a way that results in highly unbalanced partitions, such as picking the
smallest or largest element as the pivot.

L'algorithme formel de la méthode Divide et Impera :

fonction divimp (x)
{renvoie une solution pour le cas x}
if x est suffisamment petit then return adhoc(x)
{décomposer x en sous-cas x1, x2,…, xk}
 for i ← 1 to k do yi ← divimp(xi)
{recomposer y1, y2, …, yk afin d'obtenir la solution y pour x}
return y
où adhoc est le sous-algorithme de base utilisé pour résoudre de petits sous-cas du
problème donné.

HEAP CORRUPTION DETECTED:

CRT detected that the application wrote to memmory after end of heap buffer

Mergesort
Quicksort