SORTAREA PRIN ASAMBLARE - HEAP SORT

Se numeşte ansamblu (heap) a secvenţă de chei h1, h2,..., hn ce satisfac condiţiile:

hi <= h2i si hi <= h2i+1 i=1,N/2.

Se aduce tabloul la forma unui ansamblu, adică pentru orice i,j, k din intervalul [1,N], unde j=2*i si k=2*i+1, să avem :

a[i]<=a[j] si a[i]<=a[k] (*).

Se observă că în acest caz a[1] este elementul cu cheia minimă în tablou. Se interschimbă elementele a[1] şi a[N] şi se aduce subtabloul a[1],...,a[N-1] la forma de ansamblu, apoi se interschimbă elementele a[1] si a[N-1] şi se aduce subtabloul a[1],...,a[N-2] la forma de ansamblu ş.a.m.d.

În final rezultă tabloul ordonat invers. Dacă se schimbă sensul relaţiilor în condiţiile (*) atunci se obţine o ordonare directă a tabloului (a[1] va fi elementul cu cheia maximă).

Aducerea unui tablou la forma de ansamblu se bazează pe faptul că subtabloul a[N/2+1],...,a[N] este deja un ansamblu (nu există indicii j si k definiţi ca mai sus). Acest subtablou se va extinde mereu spre stânga cu câte un element al tabloului, pâna când se ajunge la a[1]. Elementul adăugat va fi glisat astfel încât subtabloul extins să devină ansamblu.

Funcția Deplasare(s,d) realizează glisarea elementului a[s] astfel că subtabloul a[s],...,a[d] (s<d) să devină ansamblu. Această procedura este folosită mai întâi pentru aducerea întregului tablou la structura de ansamblu şi apoi pentru ordonarea tabloului conform metodei enunţate mai sus.

Timpul de execuţie al sortării este O(N*log N).

Exemplu

Dorim să sortăm un şir de cinci valori de tip întreg:

Tablou: 9 1 7 0 3

Indici: 1 2 3 4 5

s=3 d=5 deplasare(2,5) rezultă tabloul: 9 3 7 0 1

s=1 d=5 deplasare(1,5) nu se efectuează deplasarea

s=1 d=4 deplasare(1,4) rezultă tabloul: 7 3 1 0 9

s=1 d=3 deplasare(1,3) rezultă tabloul: 3 0 1 7 9

s=1 d=2 deplasare(1,2) rezultă tabloul: 1 0 3 7 9

s=1 d=1 deplasare(1,1) rezultă tabloul: 0 1 3 7 9 – vector sortat

Algoritm descris în pseudocod

Deplasare(s,n)

i ← s j ← 2*i x ← a[i] ok ← adevărat

cât timp j≤d şi ok≠0 execută

dacă j<d atunci

dacă a[j]<a[j+1] atunci

j ← j+1

sfârşit dacă

sfârşit dacă

dacă x< a[j] atunci

a[i] ← a[j] i ← j j ← 2*i

altfel ok ← 1

sfârşit dacă

sfârşit cât timp

a[i] ← x

Sfărşit subalgoritm

HeapSort

s ← [n/2]+1 d ← n

cât timp s>1 execută

s ← s-1

Apel Deplasare(s,n)

Sfârşit cât timp

Cât timp d>1 execută

x ← a[1] a[1] ← a[d]

a[d] ← x d ← d-1

Apel Deplasare(s,n)

Sfârşit cât timp

Sfârşit subalgoritm

Implementare în C++

void Deplasare(int s,int n)

{

int i,j,ok; i=s; j=2*i; x=a[i];ok=0;

while((j<=d)&&(!ok))

{

if(j<d)

if(a[j]<a[j+1])

j=j+1;

if(x<a[j])

{ a[i]=a[j];i=j;j=2*i; }

else ok=1;

}

a[i]=x;

}

void HeapSort()

{

s=(n/2)+1;d=n;

while(s>1) {

s-=1;

Deplasare(s,n);}

while(d>1)

{ x=a[1];a[1]=a[d]; a[d]=x;d-=1;

Deplasare(1,d);

}

}