Kümeleme Sıralama ( Heap Sort )

Kümeleme algoritması özyinemeli olmaması sebebiyle birleştirmeli algoritmasına göre daha hızlı çalışan bir sıralama algoritmasıdır. Bu algoritmada kullanılan dört teknik terim vardır kök ( root ), birey (parent) , child (çocuk) , düğüm (node).  Bu kavramları şekil üstünde görelim.


Heap Sort

Şekil-1 : Ağaç yapısı

root

Şekil-2 : Kök

Burada 2 ve 3 no lu elemanlar 1 ‘ no lu elemanın çocuklardır. 1 no lu elemanda ağacın en tepesinde bulunduğundan buna kök denir. Ayrıca 1 no lu eleman 2 ve 3 no lu elemanın birey’idir (parent) . Ağaç yapısı kuralına göre birey’in değeri her zaman çocuklardan daha fazla olmalıdır. Şimdi bu ağcın nasıl oluşturulduğunu adım adım görelim.

step step heap sort

Şekil-3 : Adım Adım Heap Sıralaması

Örneğin (a) gibi bir ağacımız olsun. Bu ağaç oluşturulurken kök’e en büyük eleman yerleştirilir. Sonra kökün elemanları ile 2. büyük eleman kök ile yer değiştirilir ve kök ağacın en sonuna gider yan ayrılır. Bu işlem tüm ağaç boyunca sürer. Örneğin kökte 16 elemanı var ikinci büyük elemanımız 14 tür. 14 ile 16 yer değiştirir ve 16 ağaçtan ayrılır. Daha sonra 14’e bağlı 2. büyük eleman yani 10 kök ile yer değiştir. Bu işlem ağaç bitene kadar devam eder. Şimdi örnek işlemi kodlayarak görelim :

 
 using System;
  class heapSort
  {
 
    public void sort(int [] dizi)
    {
      int turSayısı;
      int gecici;
	  // sıralama işlemi burda başlıyor
      for (turSayısı=((dizi.Length / 2) - 1);turSayısı>=0; turSayısı--)
      {
        yıg(turSayısı, dizi.Length,dizi);
      }
 
      for (int i = dizi.Length - 1; i >= 1; i--)
      {
        gecici = dizi[0];
        dizi[0] = dizi[i];
        dizi[i] = gecici;
        yıg(0, i - 1,dizi);
      }
    }
 
    public void yıg(int kok, int altDugum,int [] dizi)
    {
      //yığma işlemi burada başlıyor düğümlerdeki elemanlar karşılaştırılıyor
     // ve bir üst düğüme kaydırılıyor
      bool islemTamam = false;
      int dugumSayısı;
      int gecici;
 
      while ((kok * 2 <= altDugum) && (!islemTamam))
      {
        if (kok * 2 == altDugum)
          dugumSayısı = kok * 2;
        else if (dizi[kok * 2] > dizi[kok * 2 + 1])
          dugumSayısı = kok * 2;
        else
          dugumSayısı = kok * 2 + 1;
 
        if (dizi[kok] < dizi[dugumSayısı])
        {
          gecici = dizi[kok];
          dizi[kok] = dizi[dugumSayısı];
          dizi[dugumSayısı] = gecici;
          kok = dugumSayısı;
        }
        else
        {
          islemTamam = true;
        }
      }
    }
 
    public void yazdır(int [] dizi)
 {
 
	foreach (int sayılar in dizi) {
		Console.Write(sayılar+"  " );
	}
	Console.WriteLine("\n");
 }
 
    public static void Main()
    {
 
      heapSort heap = new heapSort();
	  int [] dizi={3,44,11,55,6,77,9,111,49};
	  Console.WriteLine("\n");
      Console.Write(@" Sıralanmaış dizi elemanları : ");
	  heap.yazdır(dizi);
	  heap.sort(dizi);
      Console.Write(@" Sıralan dizi elemanları     : ");
	  heap.yazdır(dizi);
 
    }
 
  }// end class

Kaynak kod ve makale için tıklayınız..