Page 42 - MATINF Nr. 3

42 C. B˘alc˘au

Exemplul 3. Consider˘am algoritmul de sortare prin insert , ie direct˘a:

SORTINSDIR(A, n) :
for i = 2, n do
x ← A[i];
j ← i − 1;
while x < A[j] and j ≥ 1 do
A[j + 1] ← A[j];
j ← j − 1;
A[j + 1] ← x;

Arborele de sortare asociat algoritmului pentru n = 3 este reprezentat ˆın figura urm˘atoare.

1?2

≤ >

2?3 1?3
> >

1?3 2?3

Observ˘am c˘a algoritmul nu cont , ine instruct , iuni redundante.

Definit , 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, s , i fie T (A) arborele de sortare corespunz˘ator. Extindem ar-
borele binar T (A) la un arbore binar strict T (A) astfel: orice nod al lui T (A), avˆand eticheta
i?j, este reprezentat ˆıntr-un cerc s , i devine nod intern ˆın T (A) prin aplicarea urm˘atoarelor dou˘a
reguli:

• dac˘a nodul nu are descendent stˆang i se adaug˘a un descendent stˆang, reprezentat ˆıntr-un
dreptunghi, corespunz˘ator cazului a i ≤ a j , s , i etichetat cu permutarea σ a mult ,imii de indici
{1, 2, . . . , n} pentru care lant ,ul de la r˘ad˘acin˘a la nodul ad˘augat corespunde ordinii

a σ(1) ≤ a σ(2) ≤ . . . ≤ a σ(n) ;

• dac˘a nodul nu are descendent drept i se adaug˘a un descendent drept, reprezentat ˆıntr-un
dreptunghi, corespunz˘ator cazului a i > a j , s , i etichetat cu permutarea σ a mult ,imii de indici
{1, 2, . . . , n} pentru care lant ,ul de la r˘ad˘acin˘a la nodul ad˘augat corespunde ordinii

a σ(1) ≤ a σ(2) ≤ . . . ≤ a σ(n) .

Arborele T (A) se numes , te arbore extins de sortare.
Observat ,ia 3. Deoarece algoritmul A este aplicabil pentru orice permutare a vectorului
A = (a 1 , a 2 , . . . , a n ) s , i nu cont , ine instruct , iuni redundante, rezult˘a c˘a ˆın arborele extins de
sortare T (A) fiecare permutare σ a mult , imii de indici {1, 2, . . . , n} apare exact o dat˘a ca
etichet˘a a unui nod extern, deci acest arbore are n! noduri externe. Cum, conform Propozit , iei 2
din [2], orice arbore binar strict cu p noduri interne are p + 1 noduri externe, rezult˘a c˘a arborele
T (A) are n! − 1 noduri interne.