Page 41 - MATINF Nr. 3

Complexitatea algoritmilor de sortare

Costel B˘alc˘au 1

ˆ
In acest articol vom analiza complexitatea algoritmilor de sortare bazat , i pe comparat , ii de
chei. Pentru aceasta vom utiliza rezultate de baz˘a din teoria algoritmilor privind ordinele de
complexitate s , i arborii binari strict , i, prezentate ˆın [2], dar s , i dou˘a rezultate clasice din analiza
matematic˘a - Teorema lui Lagrange s , i Criteriul cles , telui.

Rezultatele ce vor fi obt , inute sunt esent , iale ˆın studiul eficient , ei s , i optimalit˘at , ii metodelor
uzuale de sortare (prin select , ie, interschimbare, num˘arare, insert , ie, interclasare, Quicksort, etc.).

Problema sort˘arii este urm˘atoarea: pentru un vector A = (a 1 , a 2 , . . . , a n ) dat, n ≥ 1, s˘a
se ordoneze cresc˘ator (sau descresc˘ator) elementele acestui vector.

Observat ,ia 1. Pentru evaluarea complexit˘at , ii algoritmilor care rezolv˘a problema sort˘arii, vom
analiza numai comparat , iile ˆın care intervin elemente ale vectorului A, numite comparat ,ii de chei.
De asemenea, consider˘am c˘a aceste comparat , ii se efectueaz˘a succesiv (comparat , iile simultane
pot fi separate).

Observat ,ia 2. Fie A un algoritm de sortare, bazat pe comparat , ii de chei, a unui vector
A = (a 1 , a 2 , . . . , a n ), n ≥ 1. Presupunem c˘a algoritmul nu cont , ine instruct , iuni redundante s , i
este aplicabil pentru orice pozit , ionare posibil˘a a componentelor vectorului A, adic˘a pentru orice
permutare a acestora.

Atunci algoritmului A i se poate asocia un arbore binar T (A) ˆın care fiecare nod are o
etichet˘a de forma i?j, construit recursiv astfel: dac˘a prima comparat , ie efectuat˘a de algoritm
este ˆıntre elementele a i s , i a j ale vectorului, atunci

• r˘ad˘acina arborelui este etichetat˘a cu i?j;

• subarborele stˆang corespunde continu˘arii algoritmului ˆın cazul a i ≤ a j , dac˘a acest caz este
posibil dup˘a prima comparat , ie (altfel este vid, adic˘a nu exist˘a descendent stˆang);

• subarborele drept corespunde continu˘arii algoritmului ˆın cazul a i > a j , dac˘a acest caz este
posibil dup˘a prima comparat , ie (altfel este vid, adic˘a nu exist˘a descendent drept).

Definit , ia 1. Arbore binar T (A) construit ˆın observat ,ia anterioar˘a se numes , te arborele de
sortare sau arborele de decizie al algoritmului de sortare A.

1
Conf. univ. dr., Universitatea din Pites , ti, cbalcau@yahoo.com

41