HEAPSORT QUICKSORT

   Heapsort ve quicksort ‘sıralama’ algoritmasıdır.

ØHeapsort max heap ve min heap olarak ikiye ayrılır.

ØHeapsort verilen değerlere göre arka planda bir ağaç oluşturur.

ØBir örnek ile açıklayacak olursak

•Örneğin heapsortta 15, 19, 10, 7, 17, 16 sayılarını gösterecek olursak ağaç modeli aşağıdaki gibi olur.

 

 

•Bu sayılarımızı max heap e göre düzenleyelim;

•Üstteki yani ata’lardaki sayıların, çocuklarından küçük olup olmadığı kontrol edilir 

•Min heapte ise tam tersi yani atalardaki sayılar daha küçük olup olmadığı kontrol edilir.

•

•16 ve 10 sayısı kontrol ediliyor max heap örneği verdiğimiz ve atanın büyük olması gerektiği için 16 sayısı yukarı alınıyor.

•

•Diğer ailemizin sıralamasını da kontrol ediyoruz

•19 sayısı 7 ve 17den büyük olduğu için doğru bir sıralamadır.

•Son ailemiz 15, 19 ve 16 ailemizi kontrol ediyoruz.

•Amacımız atadaki sayının daha büyük olması olduğu için 19 sayısı ata’ya gelecektir.

•Algoritmamızda önceki adımda 19 yerine 15  geldiği için 15. ailemizi kontrol ediyoruz.

•Max heapte büyük sayının ata’da olması gerektiği için 17 sayısını yukarı alıyoruz.

•15 ve 17 sayısını yer değiştirdik

•17 ata’ya geldi.

•Eleman silme ve diziyi düzenleme işlemine geldiğimiz zaman kökteki sayıyı yani 19 sayısını dışarı alıyoruz ve en alttaki sayıyı köke getirip max veya min heap özelliğine uyup uymadığını kontrol ediyoruz.

 

•19 sayısını silip dizide son sıraya ekliyoruz

•17 sayısı köke gelip 15 ata oluyor

•17 sayısını silip çocuklarından hangisi daha büyükse onu köke getiriyoruz.

•17 sayısını diziye ekleyeceğiz.

•16 sayısı daha büyük olduğu için köke geliyor.

•16 sayısını siliyoruz ve hangisinin köke gelmesi gerektiğini kontrol ediyoruz.

•16 sayısını diziye ekliyoruz.

•15 sayısı daha büyük olduğu için köke geliyor.

•15 sayısını siliyoruz.

•Çocuklarına bakıyoruz hangisi büyükse o köke gelecek

•10 daha büyük olduğu için köke geliyor.

•Daha sonra kökteki sayıyı siliyoruz. 

•Son hali böyle oluyor

Quicksort’ta sıralama algoritmasıdır.

88,31,52,25,98,14,30,62,23,79 sayılarını örnek olarak alalım:)

•Pivot değer bulmamız gerekiyor ilk eleman son eleman veya rastgele herhangi bir sayı olabilir.

•Bu ortadaki sayıya pivot da denilmektedir.

•Pivot değerimiz 52’ dir.

•

•Algoritmayı tekrardan pivot değerden küçük ve büyük olarak sınıflandırıyoruz

•Bu parçala fethet yaklaşımıdır.

•

•İkiye ayırdığımız sağ ve sol taraftaki parçaları tekrardan ayrı ayrı olarak ikiye ayırıyoruz.

•Birinci grup 25 ikinci grup 79 olmuştur.

ØÖnceki adımda 25 ve 79 olarak ayırdığımız grupları tekrardan orta değerden büyük ve küçük olarak ayırıyoruz.  

ØÖrneğin 14 ve 23 te 23 sayısını seçiyoruz 14 < 23 tür ve diğer adımlarda bu şekilde devam edilmiştir.

ØSonuç olarak sıralamamız 14, 23, 25, 30, 31, 52, 62, 79, 88, 98 dir