今さらながらクイックソート

どの本でも再帰の章には必ずといってもいいほどクイックソートが紹介されている．もううんざりするほどクイックソートの説明を読んできたつもりだが，Lisperの後輩がRubyでLispライクにクイックソートのコードを書いてきやがった．というのが半年くらい前にあったのだけれど，ようやくそれが理解できた．

理解できた瞬間に，Lispコードが頭の中に浮かんだ．そういうことだったのか・・・．この年になってようやく再帰というものの本質を垣間見たような気がします．

一時変数を置いてあるので，あまり関数型っぽくないごり押しLispコード

(defun quicksort (lis)
  (and lis
       (let ((oldlis (cdr lis)) (pivot (car lis)) (lis1 nil) (lis2 nil))
	 (loop
	   (cond ((null oldlis)
		  (return (append (quicksort lis1)
				  (cons pivot (quicksort lis2))))))
	   (cond ((> (car oldlis) pivot) (setq lis2 (cons (car oldlis) lis2)))
		 (t (setq lis1 (cons (car oldlis) lis1))))
	   (setq oldlis (cdr oldlis))))))