HEAPSORT QUICKSORT

      YAZININ AMACI VE KONUSU 

              Yazımın amacı Heapsort algoritmasının tanımı, algoritması, heap algoritmasının nasıl oluştuğu, max heap ve min heap örnekleri, quıck sort algoritmasının tanımı algoritmasının gidiş yolları ve algoritmasını içermektedir. Heap sort ve quıck sort algoritmalarını kıyaslayarak avantaj ve dezavantajlarını açıkladım. Her yöntemin ayrı ayrı algoritmasını yazdım.

     TANIMLAR VE KISALTMALAR 

             Heapsort: Yığın sıralaması anlamına gelir.

             Max heap: Maximum şekilde düzenlenen ( oluşturulan ) heap anlamına gelir.

              Min heap: Minimum şekilde düzenlenen ( oluşturulan ) heap anlamına gelir.

              Heapify: Algoritmanın düzeltilmesi anlamına gelir.

              Quıcksort: Hızlı sıralama anlamına gelir.

         GENEL TANIM

             Heapsort verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından 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. Ağacın en üstündeki sayıyının yani atasının çocuklarından büyük ya da küçük olup olmadığını max heap veya min heap e göre kontrol eder. Eğer seçtiği yönteme uygunsa devam eder diğer düğümleri de bu şekilde kontrol eder. Ağaç yapısı büyüklük küçüklük sıralamasına uygun olana kadar devam eder. Ekleme işlemi yapmak istiyorsak algoritmada boş bulduğu ilk yere sayıyı ekleyecektir ya da ekleyebiliriz. Ekledikten sonra atasını kontrol ediyoruz büyüklük küçüklük durumuna göre max heap veya min heap e göre atasından küçükse veya büyükse heapify ediyoruz. Silme işlemi yapmak istediğimiz zaman ise kökten yapabiliriz. En sondaki elemanı köke getiriyoruz ve kökteki eleman siliniyor (diziye aktarılabilir) . Yeni eklediğimiz eleman min heap ise çocuklarından küçük mü diye kontrol ediyoruz. Büyük ise çocuklarından küçük olanla yer değiştiriyoruz bu işlem atası daha küçük çocuk daha büyük olana kadar devam ediyor. Max heap te ise tam tersi oluyor yeni eklenen elaman çocuklarından büyük mü diye kontrol ediliyor büyükse işlem yapılmaz küçükse çocuklarından büyük olanla heapify edilir. Sıralama doğru olana kadar devam edilir. Silme işleminin maliyeti O( log N ) dir. Quıcksort ise yine verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından bir tanesidir. Basitçe sıralanacak olan dizideki orta noktada bulunan bir sayıyı seçerek diğer bütün sayıları bu orta sayıdan büyük veya küçük diye sınıflayarak sıralama yapar. Bu açıdan bir “parçala fethet” yaklaşımıdır. Ayrıca bu seçilen orta noktaya eksen (pivot) adı da verilir çünkü bütün diğer sayılar bu sayının ekseninde sıralanacaktır.

         

       YAZILIM GEREKSİNİMLERİ

             Benim araştırma konumda kod olmayıp sadece algoritma olduğu için algoritmalarımı paintte yaptım.

               ALGORİTMALAR

QUICKSORT ALGORİTMALARIM 

1.Algoritma

 

2.Algoritma

 3.Algoritma

4.Algoritma

  

HEAPSORT ALGORİTMALARI

Aşağıda işleyiş sırasına göre verilmiştir.

 

      - Kodlar

           Heapsort kodumuzu bu şekilde yazabiliriz.

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

    }

  }

            Quıcksort kodumuzu ise bu şekilde yazabiliriz.

public class HizliSiralama {

       public static void main(String[] args) {           

             int []dizi={9,5,12,7,3,21};

             hizliSirala(dizi, 0, dizi.length-1);            

             for (inti = 0; i < dizi.length; i++)

             System.out.print(dizi[i]);

       }

      

       public static int[] hizliSirala(intdizi[], intsol, intsag)

       {

             intpivot, gecici, i,j;

             i=sol;

             j=sag;           

             pivot=dizi[(sol+sag)/2];            

             do {

                    while(dizi[i]<pivot&& i<sag)

                           i++;

                    while(pivot<dizi[j]&&j>sol)

                           j--;

                    if(i<=j){                        

                           gecici=dizi[i];

                           dizi[i]=dizi[j];

                           dizi[j]=gecici;

                           i++;

                           j--;  

                    }                                      

             } while (i<=j);

        

             if (sol<j) hizliSirala(dizi, sol, j);

             if (i<sag) hizliSirala(dizi, i, sag);

                 

             returndizi;

       }            

}

      SONUÇ

            Sonuç olarak heap sort un tanımını yaptık açıkladık max heap ve min heap i açıkladık özelliklerinden bahsettik heap te ağaç oluşturma yolunu gösterdik ağaçta veriyi kontrol etme, veri ekleme ve veri silme yollarını gösterdik. Algortimalarını gösterdik. Quicksort algorimasını, gidiş yolunun nasıl olduğunu ve algoritmalarını gösterdik.

    KAYNAKLAR

              Heapsort ve quıcksort için Şadi Evren Şeker’in internet sitesi “http://bilgisayarkavramlari.sadievrenseker.com/” dan yararlandım.

              Heapsort ve quıck sort için Ali Koker’in internet sitesi http://alikoker.name.tr/ den yararlandım.

              Heapsort ve quıcksort için Rıfat Çölkesen’in “Veri Yapıları ve Algoritmalar” kitabından yararlandım.  

               Heapsort için “http://www.tercih.itu.edu.tr/” adresinden yararlandım.

               Heapsort için “http://www.yazilimdilleri.net/ adresinden yararlandım.