Merhabalar,
Sıralama algoritmaları yazı dizisinin üçüncüsü olan yığın sıralaması (Heap Sort) ile karşınızdayım. Bu gün heap sort’tan bahsedeceğiz.
Öncelikle sıralama algoritması nedir, sıralama algoritmaları nasıl çalışır bundan bahseden yazı dizimizin giriş alıntısını yapalım.
Sıralama ve arama tekniklerinden pek çok programda yararlanılmaktadır. Günlük yaşamımızda elemanların sıralı tutulduğu listeler yaygın olarak kullanılmaktadır. Sıralama, sıralanacak elemanlar bellekte ise içsel kayıtların bazıları ikincil bellek ortamında ise dışsal sıralama olarak adlandırılır.
Girişimizi yaptıktan sonra detaya girebiliriz.
Heap Sort ( Yığın Sıralaması )
Her düğümün çocuk düğümlerinin kendinden küçük veya eşit olma kuralını esas alır. Sıralama yapısı dizinin ilk elemanı her zaman en büyük olacaktır. Dizi üzerinde i. eleman ile , çocukları 2*i. ve ((2*i)+1) karşılaştırılıp büyük olan elemanlar yer değiştirilecektir.
Dizinin son elemanları dizinin ortasındaki elemanların çocuk düğümü olacağından bu işlem dizinin yarısına kadar yapılır. Elde edilen diziyi sıralamak için ise dizinin ilk elemanı en büyük olduğu bilindiğinde dizini son elemanıyla ilk elemanı yer değiştirilerek büyük eleman sona atılır. Bozulan diziye bu işlemler baştan sona tekrar uygulanır. Dizi boyutu 1 oluncaya kadar işleme devam edilir.
Heap Sort Performansı
•Bu algoritmanın çalışma zamanı O(n*logn)’dir.
•En kötü durumda en iyi performansını garanti eder.
•Fakat karşılaştırma döngülerinden dolayı yavaş çalışacaktır.
Heap Sort İşleyişi
heapify(dizi,i)
{
L = Left(i);
R = Right(i);
if(L<=heapsize&&[L]>x[i])
{
largest=L;
}
else
{
largest=i;
}
if(R<=heapsize&&x[R]>x[largest])
{
largest = R;
}
if(largest!=i)
{
temp=x[largest];
x[largest]=x[i];
x[i]=temp;
heapify(x, largest);
}
}
buildHeap(dizi)
{
heapsize = dizi.Length-1;
for(i=dizi.Length/2;i>0 ;i--)
{
heapify(dizi,i);
}
}
Left(i)
{
return 2*(i+1)-1;
}
Right(i)
{
return 2*(i+1);
}
Parent(i)
{
return (i-1)/2;
}
heap_Sort(dizi)
{
buildHeap(y);
for(i=heapsize;i>=0; i--)
{
temp=dizi[0];
dizi[0]=dizi[1];
dizi[i]=temp;
heapsize--;
heapify(dizi,0);
}
}
Böylelikle heap sort’unda detaylarından işleyişinden ve performansından bahsetmiş olduk. Anlamadığınız ya da eksik olduğunu düşündüğünüz kısımları yorumlar aracılığı ile bana bildirebilirsiniz.
Teşekkürler!
