Soru: Bir listeyi alıp hızlı sıralama algoritmasına göre (quick sort algorithm) sıralayan kodu yazınız.
Çözen : Şadi Evren ŞEKER
Çözüm:
Hızlı sıralama algoritması hatırlanacağı üzere parçala fethet (divide and conquere) yaklaşımı kullanmaktadır. Buna göre problem önce iki parçaya bölünür ve her iki parça kendi içerisinde sorun çözülene kadar parçalanır. En sonunda tek eleman kalınca problem çözülür ve sonuçlar birleştirilir.
Kodumuzu yazarken verilen bir kerteriz değerinden (pivot) büyük ve küçük sayıları toparlamak için iki ayrı fonksiyon yazacağız. Fonksiyonlardan birisi büyük sayıları, diğeri ise küçük sayıları döndürecek:
(define (larger-items alon threshold)
(cond
[(empty? alon) empty]
[else (if (>= (first alon) threshold)
(cons (first alon) (larger-items (rest alon) threshold))
(larger-items (rest alon) threshold))]))
(define (smaller-items alon threshold)
(cond
[(empty? alon) empty]
[else (if (< (first alon) threshold)
(cons (first alon) (smaller-items (rest alon) threshold))
(smaller-items (rest alon) threshold))]))
Yukarıdaki iki fonksiyonda özyineli (recursive) olarak verilen listeyi dolaşarak listedeki büyük veya küçük değerleri ayıklamaktadır. Burada iki fonksiyon arasındaki tek farkın if koşulunda bulunan >= veya < değerleri olduğuna dikkat ediniz.
Problemi bölen fonksiyonları yukarıdaki şekilde tanımladıktan sonra artık sırlama işlemini yapan fonksiyonu sayıları ayırıp birleştirmek üzere aşağıdaki şekilde yazabiliriz:
(define (quick-sort alon)
(cond
[(empty? alon) empty]
[else (append (quick-sort (smaller-items (rest alon) (first alon)))
(list (first alon))
(quick-sort (larger-items (rest alon) (first alon))))]))
Görüldüğü üzere listenin ilk elemanı kerteriz (pivot) olarak seçiliyor ve bu değerden küçükler +kerteriz + büyükler şeklinde sıralama işlemi yapılıyor.
Çözüm çalıştırması:
(quick-sort (list 11 8 8 9 9 14 8 7))
Şeklinde fonksiyona bir liste verilmesi yeterlidir.
Yukarıda örnek çalışma verilmiştir buna göre verilen listenin sıralanmış hali (list 7 8 8 8 9 9 11 14) olarak doğru bir şekilde bulunur.