Page 16 - REVISTA MATINF Nr. 5

16 C. B˘alc˘au

Descrierea ˆın pseudocod a algoritmului are urm˘atoarea form˘a.

SORTINT(A, p, u) : // sortarea secvent , ei (a p , . . . , a u )
if p < u then
p + u
j k
m ← ;
2
SORTINT(A, p, m); // sortarea subsecvent , ei (a p , . . . , a m )
SORTINT(A, m + 1, u); // sortarea subsecvent , ei (a m+1 , . . . , a u )
INTERCLAS(A, p, u, m); // interclasarea celor dou˘ a subsecvent , e sortate

unde procedura de interclasare este:

INTERCLAS(A, p, u, m) ; // interclasarea subsecvent , elor
// (a p , . . . , a m ) s , i (a m+1 , . . . , a u ), sortate cresc˘ ator
i ← p; // pozit , ia curent˘ a din subsecvent , a (a p , . . . , a m )
j ← m + 1; // pozit , ia curent˘ a din subsecvent , a (a m+1 , . . . , a u )
k ← 0; // dimensiunea curent˘ a a unui vector B, sortat cresc˘ ator,
// ce va fi construit prin interclasarea celor dou˘ a subsecvent , e,
// comparˆ and componentele curente a i s , i a j din cele dou˘ a subsecvent , e
// s , i copiind-o pe cea mai mic˘ a ˆ ın B
while i ≤ m and j ≤ u do
// mai exist˘ a componente necopiate ˆ ın ambele subsecvent , e
if A[i] ≤ A[j] then
// mai mic˘ a este componenta curent˘ a din prima subsecvent ,˘ a,
k ← k + 1; B[k] ← A[i]; // deci o copiem ˆ ın B
i ← i + 1; // s , i avans˘ am ˆ ın prima subsecvent ,˘ a
else
// mai mic˘ a este componenta curent˘ a din a doua subsecvent ,˘ a,
k ← k + 1; B[k] ← A[j]; // deci o copiem ˆ ın B
j ← j + 1; // s , i avans˘ am ˆ ın a doua subsecvent ,˘ a

// una dintre subsecvent , e nu mai are elemente necopiate;
// copiem ˆ ın B s , i componentele r˘ amase necopiate
// din cealalt˘ a subsecvent ,˘ a
for q = i, m do // componente r˘ amase necopiate ˆ ın prima subsecvent ,˘ a
k ← k + 1; B[k] ← A[q];
for q = j, u do // componente r˘ amase necopiate ˆ ın a doua subsecvent ,˘ a
k ← k + 1; B[k] ← A[q];
// La final aducem componentele (sortate cresc˘ ator) din B = (b 1 , . . . , b k )
// ˆ ınapoi ˆ ın subsecvent , a (a p , . . . , a u ):
for i = 1, k do
A[p + i − 1] ← B[i];

Apel:

SORTINT(A, 1, n) // pentru sortarea ˆ ıntregului vector A = (a 1 , . . . , a n ).

ˆ
Exemplul 1. In figura urm˘atoare este reprezentat arborele extins de sortare asociat algoritmului
de sortare prin interclasare pentru n = 3. Observ˘am c˘a algoritmul nu cont , ine comparat , ii de