Yığınlama Sıralaması (Heap Sort)

Yazan : Şadi Evren ŞEKER

Verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından (sorting algorithms) bir tanesidir. Yıpı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. (Lütfen yığın ağacındaki en büyük sayının her zaman en üstte duracağını hatırlayınız. )

Sıralanmak istenen verimiz:

5,12,20,18,4,3

olsun. Bu verilerin bir oluşumun(composition) 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.

Yukarıdaki bu sayılardan bir yığın ağacı oluşturulduğunda aşağıdaki şekilde bir sonuç elde edilir:

Bu ağacın en büyük değeri en üstte (kökte) durmaktadır öyleyse bu değer alınarak sonuç dizisinin son elemanı yapılırsa ve sonra geriye kalan sayılar tekrar yığınlanırsa (heapify) ve bu işlem eleman kalmayana kadar tekrarlanırsa sonuç dizisindeki veriler sıralanmış olarak elde edilir. Bu işlemler adım adım aşağıda gösterilmiştir:

Sonuç dizisi : {20}

20 sayısı yığın ağacından silindikten sonra kalan sayılar yığınlandıktan sonra yukarıdaki ağaç elde edilir. Bu ağacın en üstündeki sayı alınırsa sonuç dizisi : {20,18} olarak bulunur ve 18 alındıktan sonra kalan sayılar yığınlandığında ise aşağıdaki ağaç elde edilir.

Bu ağacında en üstünde bulunan sayı 12′dir ve bu sayı sonuç dizisine eklenir. Sonuç dizisi : {20,18,12} olarak bulunur ve kalan sayılar bir kere daha yığınlanır:

Sonuçta kalan sayıların yığınlanmasıyla yukarıdaki ağaç elde edilir ve bir kere daha en üstteki sayı alınarak sonuç dizisi : {20,18,12,5} olarak bulunur.

Aynı işlem kalan sayılara tekrar tekrar uygulanarak {20,18,12,5,4,3} sayıları elde edilir. Dikkat edilirse bu sayılar ilk başta verilen sayıların sıralanmış halidir. Şayet sıralama işlemi küçükten büyüğe yapılsın isteniyorsa bu durumda sayılar dizinin başından değil sonundan yazılarak kaydedilebilir veya çıkan sonuç tersten sıralanabilir.

Bu işlemi yapan bir yığın sıralaması (heap sort) kodu java dilinde aşağıdaki şekilde yazılabilir :

public void heapsort(int[]A){
    int tmp;
    BuildHeap(A);
    for(int i = A.length-1; i>=0; i--)
    {
     tmp=A[0];
     A[0]=A[i];
     A[i]=tmp;
     heapsize = heapsize -1 ;
     heapify(A,0);

    }
  }

Bu kodun diğer fonksiyonları için yığın ağacı (heap) başlıklı konuyu okuyabilirsiniz.

« Yığın Ağacı (Heap) | Birleştirme Sıralaması (Merge Sort) »

Yorumlar

Toplam 2 yorum var.

Anonymous | 27 Dec 2009, 22:55
İlk ağaç şemasında zaten nerdeyse tüm dizi sıralanmış ahlde duruyor. Aslı mesele dizin o ağaç şekline naısl geldiği ?
Şadi Evren ŞEKER | 27 Dec 2009, 23:28
Yukarıdaki bu yazı sadece yığın sıralamasını (heap sort) açıklamaktadır. Yazının içerisinde de bağlantı (link) olduğu üzere, yığının oluşturulması

http://bilgisayarkavramlari.com/2008/08/09/yigin-agaci-heap/

Yukarıdaki yazıda açıklanmıştır.

başarılar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Yığınlama Sıralaması (Heap Sort)' isimli yazı 09 Aug 2008 tarihinde, saat: 21:36 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 2928 defa okunmuştur.

Benzer yazıları JAVA, algoritma analizi (teory of algorithms), veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar