Sayfa 12

(pass) yapılmakta ve sıralama ilerledikçe taramalar giderek kısalmaktadır. Ancak bu kez eldeki öge onun hemen üstündekiyle kıyaslanmak yerine o özel (particular) taramada en üstte

bulunan öge ile kıyaslanmakta ve eğer gerekiyorsa söz konusu ögenin yeri değiştirilmektedir. Bu işleme biçiminin tam da “Ayıklamalı Sıralama” deyişine uygun düştüğünü söyleyebiliriz;

SOLDAKİNİ |...

zira dikkat edildiğinde her taramada listenin en üstünde bulunan ögenin bütün listenin içinden (buna en üstteki de dahil) seçilip alındığı görülebilir. Çizim-3'te gösterilen minyatür dizinin incelenmesi halinde bu söylediğimiz daha iyi anlaşılabilir. Sonuç olarak Ayıklamalı Sıralamada da Kabarcık sıralama ile aynı sayıda kıyaslama yapılması gerekmekte ancak gerçekleştirilen yer değiş tokuşu daha az sayıda kalmaktadır. Bu nedenledir ki aynı sayıda kaydın söz konusu olduğu bir durumda Ayıklamalı Sıralama daha kısa zamanda sonuç verir.

Çabuk ya da İkili Sıralama

Buraya dek sözünü ettiğimiz ve bir veriler dizisini sıralamaya yarayan her üç yöntem de temelde aynı ilkeye dayanmaktaydılar. Programın veriler üstünden sonlu bir sayıda tarama yapmasını sağlayan, içiçe yerleştirilmiş iki döngü kullanılır ve her taramanın sonunda tek bir eleman doğru haneye yerleştirilerek sonraki taramalarda hesaba katılmaz. Bu, yerleştirilmesi gereken hiçbir öge kalmayana kadar devam eder. Çabuk sıralama ise değişik bir kavrama dayanılarak geliştirilmiş bir yöntemdir. Dizideki ilk öge bir tür “başlama öbeği” ya da bir başka deyişle “pivot” olarak alınır ve diğer ögeler onunla kıyaslanırlar. Bu eldeki pivottan daha küçük olan bütün ögeler pivotun üstüne, daha büyük olanlarsa altına yerleştirilirler. Bu yolla, dizinin eski halinde en başta bulunan kayıt doğru haneye yazılmış olur ve diğer kayıtlarda ona göre doğru tarafta (altında ya da üstünde) yerlerini almış olurlar. Aynı prosedür (yordam) şimdi bu kaydın üstünde ve altında kalan kümelere ayrı ayrı uygulanır. Prosedür bu şekilde giderek küçülen alt kümelere uygulanmaya devam edilir ve sıralanacak alt küme tek bir ögeden ibaret kaldığında durdurulur. Sıralanacak hiçbir alt küme kalmadığında (ya da bütün alt kümeler tek bir ögeye indirgendiklerinde) dizinin bütünü de sıralanmış olacaktır. Sanırız bu yöntemin en iyi açıklamasını Çizim-4'te bulacaksınız.

Çizimi incelediğinizde iki gösterge (pointer) kullanılmış olduğunu göreceksiniz. Bunlardan biri gündemdeki kaydı gösterirken diğeri de dizideki kullanılabilir alanı gösterir. İlk aşamada göstergeler kümenin her iki ucuna yerleştirilmiştir. P1 göstergesi tarafından gösterilen eleman, doldurduğu hanenin üstüne yeni kayıt yapılabilecek biçimde, ayrı bir değişkene saklanmıştır. Kıyaslamalar şimdi P2 göstergesi tarafından gösterilen elemandan başlar: TAVUK KURT böylece P2 göstergesi eksiltilir. FARE KURT, böylece ZEBRA yerleştirilir ve bu noktadan aşağıya doğru işlem sürdürülür. ZEBRA KURT, bu yolla ZEBRA P2'ye yerleştirilir. Şimdi de işleme P2'den yukarıya doğru devam edilecektir. ARI KURT, böylece ARI P1'e yerleştirilir. Göstergeler artık buluşmuşlardır ve pivot, yani KURT bu noktaya yerleştirilebilir. Bu noktanın biri üstünde, biri de altında olmak üzere iki alt küme çıkmıştır ortaya ve her ikisine de şimdi ayrı ayrı Çabuk sıralama yordamını (routine) uygulamak gerekmektedir.