Page 17 - REVISTA MATINF Nr. 5

Complexitatea algoritmului de sortare prin interclasare (mergesort) 17

chei redundante.

1?2
≤ >

1?3 2?3
≤ > ≤ >

2?3 (3,1,2) 1?3 (3,2,1)

≤ > ≤ >

(1,2,3) (1,3,2) (2,1,3) (2,3,1)

Observat ,ia 1. Procedura de interclasare poate fi us , or ˆımbun˘at˘at , it˘a, eliminˆand copierile inutile
ˆın vectorul intermediar B s , i ˆınapoi ˆın vectorul A ale componentelor r˘amase necopiate (la ies , irea
ˆ
din ciclul while) ˆın una dintre cele dou˘a subsecvent , e interclasate. In acest sens, putem renunt , a
la ciclul for q = j, u, deoarece elementele r˘amase necopiate ˆın a doua subsecvent , ˘a sunt deja
pe pozit , iile bune, deci nu are rost s˘a le mai copiem ˆın B. De asemenea, elementele r˘amase
necopiate ˆın prima subsecvent , ˘a pot fi copiate direct pe ultimele pozit , ii ale secvent , ei (a p , . . . , a u )
(ˆın ordine invers˘a, pentru a evita pierderea valorilor unor componente prin suprapunere), f˘ar˘a a
le mai copia ˆın B; pentru aceasta, putem ˆınlocui ciclul for q = i, m cu:

for q = m, i, −1 do
A[u + q − m] ← A[q];

Observat ,ia 2. Implementarea aleas˘a pentru algoritmul de sortare prin interclasare este una
recursiv˘a, ˆın care solut , ia problemei apeleaz˘a solut , iile subproblemelor de dimensiuni mai mici,
ˆ
adic˘a foloses , te strategia Divide et Impera ˆın varianta top-down. In cazul acestei vari-
ante este important c˘a subproblemele sunt disjuncte s , i astfel calculul necesar rezolv˘arii unei
subprobleme nu este reluat prin apelarea repetat˘a a acesteia (ceea ce ar conduce la un timp
de calcul exponent , ial, as , a cum se ˆıntˆampl˘a la utilizarea acestei variante ˆın rezolvarea unor
probleme prin metoda program˘arii dinamice). Ment , ion˘am c˘a algoritmul poate fi descris s , i
implementat s , i iterativ, utilizˆand varianta bottom-up a strategiei Divide et Impera, ˆın
care subproblemele se rezolv˘a ˆın ordinea cresc˘atoare a dimensiunii lor. Aceast˘a variant˘a este
mult mai eficient˘a ˆın cazul program˘arii dinamice, cˆand subproblemele se suprapun, dar ˆın cazul
sort˘arii prin interclasare are aceeas , i complexitate ca s , i varianta noastr˘a, de tip top-down. Mai
multe detalii privind implementarea s , i complexitatea acestor dou˘a forme, precum s , i a altor
variante ale algoritmului de sortare prin interclasare, pot fi g˘asite ˆın [9] s , i [8].

Complexitatea algoritmului

Teorema 1 (complexitatea algoritmului de sortare prin interclasare). Algoritmul de
sortare prin interclasare a unui vector cu n componente are complexitatea Θ(n log n).
2

Demonstrat¸ie. Fie T(n) timpul de execut , ie al algoritmului SORTINT(A, 1, n). Vom demonstra
c˘a T(n) = Θ(n log n) prin dou˘a metode.
2