qsort.scm

病み上がりなので、楽そうなのを選んだら10分で終わった。まあ、いいか。
今日のネタはクイックソート。

gosh> (qsort '(2 4 1 5 5))
(1 2 4 5 5)

{friend:hiro}あたりはクイックソートは複雑だと思っているみたいだけれども、再帰とリストを使えばとてもシンプルに書ける。複雑なのは、ループと配列を使ったバージョン。

(use srfi-1)

(define (qsort lst)
  (if (or (null? lst) (= (length lst) 1))
      lst
      (let* ((pivot (car lst))
	     (lst2 (cdr lst))
	     (before (qsort (filter (lambda(x) (< x  pivot)) lst2)))
	     (after  (qsort (filter (lambda(x) (<= pivot x)) lst2))))
	(append before (list pivot) after))))

• Schemeにはfilterはもともとないので、srfi-1を使う
• ピボットと等しい要素がいくつかある場合を、考慮に入れておこう