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);
}
}