Bu sayfadaki yazılar
Sayfanın metni
Sayfa 13
Programın çapından da görülebileceği gibi (liste 4) bu yöntem az önce ele aldığımız diğer yöntemlerden daha karmaşıktır. Her şeyden önce böyle bir sıralama yöntemi için daha fazla bellek gerekmektedir. Bunun nedeni, sadece programın göreceli olarak daha fazla yer tutması değil, aynı zamanda daha fazla değişken kullanmasıdır da. Söz gelimi henüz sıralanmamış alt kümelerin parametrelerinin saklanması için başlı başına bir deste-bellek (stack) görevlendirilmektedir. (Bir kerede ancak bir tek alt kümenin ele alınabileceğini anımsayın.) Bunların yanısıra Çabuk sıralamanın asıl çekiciliği tartışılmaz hızıdır. (Tablo-1'deki zamanlamalara bkz.) Sıralanacak ögelerin sayısı arttıkça diğer üç sıralama yönteminin gereksindikleri zaman üst sayısal (exponential) bir biçimde artarken, Çabuk sıralamanın öge başına harcadığı zaman, listenin çapı büyüse de, hemen hemen aynı kalmaktadır. Bu özellik denenmemiş bir listenin Çabuk sıralama ile ne kadar bir zamanda düzenlenebileceğini önceden kestirme olanağını verir. Bu tür bir sıralama baştan aşağı karışık yazılmış kütükleri sıralarken en etkin sonucu verecektir; ancak kısmi olarak düzenlenmiş bir kütüğe uygulandığında biraz daha yavaş çalışacağı söylenebilir. Ve dikkat! Bu seçmeye aldığımız sıralama yöntemlerinin tümü de aynı ögenin tekrarlandığı (duplicate) durumları işleme yeteneğine sahiptirler.
Uyarlamalar İçin İpuçları
Burada dikkat edilmesi gereken nokta, yukarıda listesi çıkarılmış programlarda bütün dizi alt indislerinin (subscript) sıfırdan başlamalarıdır.
Sözgelimi DIM IMFS(10) ifadesi IMFS$ için on bir hane ayırmış olmaktadır (on hane değil). Bütün sıfır elemanlar belleği tutumlu kullanmak amacıyla hesaba katılmışlardır ve bu noktanın özellikle alt indisleri 1'den başlatan aygıtlara uyarlama yaparken gözetilmesi gerekir. Gözden kaçırılmaması gereken bir başka nokta da SWAP ifadesinin (statement) kullanılışıdır. Bu ifade ardından gelen iki değişkenin içerdiklerini değiş tokuş ettirir. Böyle bir ifadeye sahip olmayan aygıtlar için “SWAP IMES(X), IMFS(Y)” satırı aşağıda gösterildiği gibi yeniden yazılabilir:
TEMP$ —- — - TEMP$
Özet Olarak Söylenebilecekler
Kabarcık sıralama: • Kısmi sıralanmış kütükler için • Dar hacimli kütükler için • Bellek kapasitesinin daha yetkin yöntemleri uygulamaya yetmediği durumlarda. Dalgacık sıralama: • Kabarcık sıralamanın kullanıldığı yerlerde Ayıklamalı sıralama: • Dar/orta hacimli kütükler için • Bellek kapasitesinin daha yetkin yöntemleri uygulamaya yetmediği durumlarda Çabuk sıralama: • Orta/büyük hacimli kütükler için • Özellikle de kısmi olarak sıralanmamış olanlar için
Klavyeyle gezinmek için ← ve → tuşları.
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.