Seyir Defteri

Heapsort Algoritması

Eyl 08, 2013
Verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından (sorting algorithms) bir tanesidir. Yığınlama sıralaması, arka planda bir yığın ağacı(heap)  oluşturur ve bu ağacın en üstündeki sayıyı alarak sıralama işlemi yapar. Bu verilerin bir oluşumun  belirleyici alanları olduğunu düşünebiliriz. Yani örneğin vatandaşlık numarası veya öğrenci numarası gibi. Dolayısıyla örneğin öğrencilerin numaralarına göre sıralanması durumunda kullanılabilir.

Algoritmanın Çalışması

Algoritma adımları şu şekilde özetlenebilir:
  1. Sayı grubundan bir ağaç oluşturulur.
  2. Bu ağaç yaprak olmayan en son elemandan ilk(kök) elemana doğru heapify metoduyla yığınlaştırılır.
  3. En üstte(kökte) duran yani en büyük olan değer alınarak sonuç dizisinin son elemanı yapılır.
  4. Sonra geriye kalan sayılar tekrar yığınlaştırılır (heapify) ve bu işlem eleman kalmayana kadar yapılırsa sonuç dizisindeki veriler sıralanmış olarak elde edilir.
  5. Bu sayı dizisi ilk başta verilen sayı dizisinin küçükten büyüğe sıralanmış halidir. Şayet büyükten küçüğe sıralanmak istenirse algoritmanın biraz değiştirilmesi gerekir.
Algoritmanın C# Web Uygulaması ve Geçen Sürenin Hesaplanması

Form ile kullanıcıdan üretilecek sayı adedinin alınır. Daha sonra yazılmış olan HeapSort() sınıfı oluşturulur. Random() sınıfı ile 0 ile 500 arasında rasgele sayılar üretilir ve dizi değişkenine atanır.

public heapSort objHeapSort,uret;
public string strSonuc;
protected void Button_Click(object sender, EventArgs e)
{
  int deger;
  if (sayi.Text == "")
    deger = 0;
  else
    deger = Convert.ToInt32(sayi.Text);

  uret = new heapSort(deger); 
  uret.RasgeleSayiUret();
  uret.elemanSayisi = uret.dizi.Length;

  //Geçen süre hesaplanıyor
  Stopwatch gecen_sure = new Stopwatch();
  gecen_sure.Start();
  uret.yigin_olustur();
  uret.sirala();
  gecen_sure.Stop();

  lblsure.Text = "Sıralanan veri sayısı : " + uret.dizi.Length + "<br />Toplam geçen süre : " + gecen_sure.Elapsed;
  if (uret.dizi.Length < 1000)
  {
    lblsonuc.Text = "";
    ArrayList sonuc = new ArrayList(uret.dizi);
    foreach (int i in sonuc)
    {
      strSonuc = strSonuc + i + ", ";
    }
  }
}

HeapSort isimli bir namespace içerisinde yigin_olustur(), heapify(), yer_degistir(), sirala() ve RasgeleSayiUret() fonksiyonları uygulamayı oluşturan metodlardır.

namespace HeapSort 
{
  public class heapSort : System.Web.UI.Page
  {
    public int elemanSayisi;
    public int enBuyuk;
    public int[] dizi;
    public Random objRasgeleSayiUret;
    public int parent(int i) { return i / 2; }
    public int sol(int i) { return (i * 2); }
    public int sag(int i) { return ((i * 2) + 1); }
    public heapSort(int a)
    {
      this.dizi = new int[a];
    }

    public void yigin_olustur() 
    {
      for (int i = (this.elemanSayisi/2); i > 0; i--)
      {
        this.heapify(i);
      }
    }

    public void heapify(int i)
    {
      int l = sol(i);
      int r = sag(i);
      if (l <= this.elemanSayisi)
      if (this.dizi[l - 1] >= this.dizi[i - 1])
        this.enBuyuk = l;
      else
        this.enBuyuk = i;
      if (r <= this.elemanSayisi)
        if (this.dizi[r - 1] > this.dizi[this.enBuyuk - 1])
          this.enBuyuk = r;
      if (this.enBuyuk != i)
      {
        this.yerDegistir(i, this.enBuyuk);
        this.heapify(this.enBuyuk);
      }
    }

    public void yerDegistir(int degisen, int yeniDeger)
    {
      int tutucu = this.dizi[yeniDeger - 1];
      this.dizi[yeniDeger - 1] = this.dizi[degisen - 1];
      this.dizi[degisen - 1] = tutucu;
    }
    public void sirala()
    {
      for (int i = this.elemanSayisi; i > 0; i--)
      {
        this.yerDegistir(1,i);
        this.elemanSayisi = this.elemanSayisi-1;
        this.heapify(1);
      }
    }
    public void RasgeleSayiUret() 
    {
      Random objRasgeleSayiUret = new Random();
      for (int i = 0; i < this.dizi.Length; i++)
      {
        this.dizi[i] = objRasgeleSayiUret.Next(0, 500); 
      } 
    }
  }
}

Uygulama çalıştırıldıktan sonra oluşan ekran görüntüsü aşağıdaki gibidir:

KATEGORİLER