Jserv's blog

用 Makefile 實現 quick sort

在大學課程中，quick sort 大概是用來闡述遞迴概念的最佳範例，因為既簡潔又實用。多數的程式語言也可採用此概念，甚至連 GNU make 裡頭 function call 也能遞迴，所以，何不試著實做 quick sort 呢？以下是 proof-of-concept 的試作品：

TRUE = 11111
gt = $(shell if [ $1 -gt $2 ] ; then echo $(TRUE); fi)
lt = $(shell if [ $1 -lt $2 ] ; then echo $(TRUE); fi)
le = $(shell if [ $1 -le $2 ] ; then echo $(TRUE); fi)

qsort = \
    $(if $(call le,$(words $1),1),$1, \
        $(call qsort, \
            $(foreach i,$1, \
                $(if $(call gt,$(firstword $1),$i), $i,))) \
    $(firstword $1) \
    $(call qsort, \
        $(foreach i,$1, \
            $(if $(call lt,$(firstword $1),$i), $i,))))

data = $(shell od -vAn -N10 -w1 -tu1 < /dev/urandom)

all:
        @echo $(call qsort, $(data))

$(data) 給定自十個隨機亂數，取於 /dev/urandom，原理是讀入二進位的亂數資料後，透過 od 指令將每一個 byte 轉換成一個無符號整數。當然重點是 "qsort"，我們可看到 Makefile 中的宣告與實做中，遞迴地呼叫自身，也就是 $(call qsort, ...) 的動作，將 "divine and conquer" 的想法予以實現：先分成左右兩半，再來排序。 取得預先準備的 [Makefile.qsort]，執行的情況類似以下輸出：

$ make -f Makefile.qsort 
2 20 29 58 88 165 172 230 242 246

既然輸入資料取於亂數，所以只要看到遞增數列即可。
由 jserv 發表於 June 28, 2008 07:27 AM