読者です 読者をやめる 読者になる 読者になる

(define -ayalog '())

括弧に魅せられて道を外した名前のないプログラマ

ふつうにクイックソートをSchemeで書いた

なんとなーく書いてみた。改めてこういうの書いてみて、アルゴリズム以外をあんまり意識しなくていいのは楽でいいなって思った。

(use util.match)
(define (take p lst c)
  (filter (lambda (x) (c p x))
	  lst))
(define (take-less p lst)
  (take p lst >))
(define (take-greater p lst)
  (take p lst <=)

(define (quick-sort lst)
  (match lst
	 [() '()]
	 [(first . rest)
	  (append (quick-sort (take-less first rest))
		  (list first)
		  (quick-sort (take-greater first rest)))]))

;;test
(quick-sort '(3 9 2 8 4 1 0))
(quick-sort '(0 0 0 0 0 1 2 2 2 2))
(quick-sort '(0 0 0 0))
(quick-sort '())

追記

take-lessかtake-greaterのどちらかに=を付けていないと、同じ数がリストに入っていると1つになってしまうので注意。(修正したんです)