HEAP SORT ALGORİTMASI

HEAP SORT ALGORİTMASI

 Heap Sort Algoritması Türkce çevirisi olarak Yığun sırlaması olarak söyleyebilriiz ve bilgisayar teknolojisinde kullanılan karşılaştırmaya dayanan sıralı bir sıralamalı bir sıralamalı algoritmasıdır ve diğer sıralamalara göre yavaş çalışması ancak en kötü durumu yani Worst case O(nlogn) olması avantajıdır

Uzun zaman aldığından, büyük veri paketlerinde kullanılmamasına dikkat edilmelidir.Çalışma sistemine gelince: Arka kısımda 2li sıralama ağacı kullanır. Tüm sıralama işlemlerini bu ağaç üzerinde gerçekleştirir.

Algoritma, verilen veri kümesini 2’li ağaca çevirir. Bu işlemi yaparken herhangi bir koşul gözetilmez, elemanlar ağaca sırayla eklenir. Fakat ağaç oluşturduktan sonra ağacın en son elemanından başlayarak köke kadar tüm elemanları tarayarak, ağacın bir MAX ya da MIN HEAP ağacı olması sağlarız. (Bu kadarı, sıralamamızı azalan ya da artan olması durumuna göre karar veririz.). Bu işlemden sonra en sondaki eleman ile kök elemanının yerlerini değiştirilir ve en son yaprak ağaçtan koparılır.

Sıralama, yer değiştirme ve koparma işlemleri, ağaçta sadece kök elemanı kalana kadar tekrarlanır. Koparılan elemanlar konduğu sırada listeye geri alınır. Böylece sıralama yapılmış olur.

Sıralama örneği:

Bize verilen dizi: 4 1 3 2 16 9 10 14 8 7

2li ağacımızı oluşturalım:

Ağacı düzenleyelim (sıralama):

 

Ağacın son elemanı ile kökü yer değiştirelim, ve son düğümü ağaçtan kopartalım.

Ağacın en son hali:

Bilgisayar kodunu verelim;

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

    }

  }