3 Mergesort (sortarea prin interclasare)
Fie T[1 .. n] un tablou pe care dorim sa-l
sortam crescator. Prin tehnica divide et impera putem proceda astfel: separam
tabloul T in doua parti de marimi cat
mai apropiate, sortam aceste parti prin apeluri recursive, apoi interclasam
solutiile pentru fiecare parte, fiind atenti sa pastram ordonarea crescatoare a
elementelor. Obtinem urmatorul algoritm:
procedure mergesort(T[1 .. n])
{sorteaza in ordine crescatoare
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)
unde insert(T) este algoritmul de sortare prin
insertie cunoscut, iar merge(T, U, V) interclaseaza
intr-un singur tablou sortat T
cele doua tablouri deja sortate U si V.
Algoritmul mergesort ilustreaza perfect principiul divide et impera:
pentru n avand o valoare mica, nu este rentabil sa apelam recursiv procedura
mergesort, ci este mai bine sa efectuam sortarea prin insertie. Algoritmul
insert lucreaza foarte bine pentru n 16,
cu toate ca, pentru o valoare mai mare a lui n, devine neconvenabil.
Evident, se poate concepe un algoritm mai putin eficient, care sa mearga pana
la descompunerea totala; in acest caz, marimea stivei este in Q(log n).
Spatiul de memorie necesar pentru tablourile auxiliare U si V
este in Q(n). Mai precis, pentru a sorta un
tablou de n = 2k elemente, presupunand ca
descompunerea este totala, acest spatiu este de
src="http://www.cwu.edu/~andonie/Cartea%20de%20algoritmi/images/cap7/cap7_2.gif" v:shapes="_x0000_i1026">
elemente.
Putem considera (conform Exercitiului 7.7) ca algoritmul merge(T, U, V)
are timpul de executie in Q(#U + #V),
indiferent de ordonarea elementelor din U si V. Separarea lui
T in U si V necesita tot un timp in Q(#U + #V).
Timpul necesar algoritmului mergesort pentru a sorta orice tablou de
n elemente este atunci t(n) t(n/2)+t(n/2)+Q(n).
Aceasta ecuatie, pe care am analizat-o in Sectiunea 5.1.2, ne permite sa conchidem
ca timpul pentru mergesort este in Q(n log n).
Sa reamintim timpii celorlalti algoritmi de sortare, algoritmi analizati in
Capitolul 5: pentru cazul mediu si pentru cazul cel mai nefavorabil insert
si select necesita un timp in Q(n2),
iar heapsort un timp in Q(n log n).
In algoritmul mergesort, suma marimilor subcazurilor este egala cu marimea
cazului initial. Aceasta proprietate nu este in mod necesar valabila pentru
algoritmii divide et impera. Oare de ce este insa important ca subcazurile sa
fie de marimi cat mai egale? Daca in mergesort il separam pe T
in tabloul U avand n-1 elemente si tabloul V avand un singur
element, se obtine (Exercitiul 7.9) un nou timp de executie, care este in Q(n2).
Deducem de aici ca este esential ca subcazurile sa fie de marimi cat mai apropiate
(sau, alfel spus, subcazurile sa fie cat mai echilibrate).
