ALGORİTMALAR VE PROGRAMLAMA - Deneme Sınavı - 1

Hızlı sıralama ve birleştirerek sıralama algoritmalarında  özyinelemeli (recursive) fonksiyon olarak yazılması söz konusudur.

Hızlı sıralamanın çalışma mantığının anlatıldığı bu örnekte (Şekil 7.4) 5 elemanlı bir dizi bulunmaktadır. Her adımda, dizinin orta elemanı pivot olarak seçilmekte ve kırmızı ile işaretlenmektedir. Bu adımla birlikte, bölümleme algoritması çalışmaya başlar. Dizinin solundan başlanarak, pivot olarak belirlenen orta elemana kadar olan sayılar içinde pivottan büyük sayı olup olmadığı kontrol edilir. Sonrasında, dizinin sağından başlanarak pivot olarak belirlenen orta elemana kadar olan sayılar içinde pivottan küçük sayı olup olmadığı kontrol edilir. Bulunan küçük ve büyük sayılar birbiriyle yer değiştirilir. Şekilde, 1. adımda 21 ve 4 değerlerinin bu gerekçeyle yer değiştirdiği görülmektedir. Bu işlem, pivot olarak belirlenen sayının solundaki tüm sayıların kendisinden küçük ve sağındaki tüm sayıların kendisinden büyük hale gelmesiyle tamamlanır. Sonuç itibariyle, pivot olan elemanın solunda ve sağında sıralı olması gerekmeyen iki adet sayı grubu yer almaktadır. Bir sonraki adımda ise dizi pivot elemanın olduğu yerden mantıksal olarak ortadan ikiye ayrılarak, iki kısım için de ayrı ayrı bölümleme algoritması uygulanır. Bu iki kısım için, kendi sayı grupları içerisinden birer pivot belirlenerek işlemler sürdürülür. En sonunda, bu iki grup da kendi içlerinde sıralı hale gelmiş olur ve iki grubun birleşmesiyle tamamen sıralı bir dizi elde edilir.

Bu örnekte, her adımda yığının en büyük elemanı bulunmakta ve sarı ile gösterilen bu eleman, ağacın kök konumuna yerleştirilmektedir. Dolayısıyla, maksimum yığın yapısının kullanıldığı söylenebilir. Her bir elemanın sarı ile boyalı olarak gösterildiği aşamalarda, ağacın daha üst seviyelerindeki düğüm noktaları alttakilerden büyük veya eşit durumda olacak şekilde yer değiştirmeler yapılmıştır. Kırmızı ile gösterilen sayılar, bu kuralın kapsamında olmayan ve üzerinde artık işlem yapılmayan düğüm noktalarıdır. Bir sonraki adımda ise sarı ile gösterilen elemanlar ağaçta en alta yerleştirilmekte ve dolayısıyla dizinin son konumlarında büyük elemanların bulunması sağlanmaktadır. Her işlem adımından sonra dizinin sonunda yer alması gereken ve kırmızı ile gösterilen eleman, sonraki sıralama işlemlerine katılmamaktadır. Şekildeki ikinci işlemde 21 sayısı en sona atıldıktan sonra, bir sonraki adımda 5 eleman yerine, kalan 4 elemanın içerisindeki en büyük sayı bulunmaktadır. İlk eleman haricindeki bütün dizi elemanları kırmızı ile işaretlendiğinde, dizi küçükten büyüğe doğru sıralı hale gelmiş olur. İlk eleman için kendisinden başka karşılaştırılacak eleman bulunmadığından algoritma bu noktada sonlandırılır.