Displaying posts written in

7月 2009

Common Lisp  | 2009 年 7 月 8 日 By | No comments yet

Common Lispマージソート

組み込みの merge を使ってマージソートを実装してみた。

(defun merge-sort (result-type seq pred &key key)
  (let* ((len (length seq))
	 (mid (floor (/ len 2))))
    (if (> 2 len)
	seq
	(merge result-type
	       (merge-sort result-type (subseq seq 0 mid) pred :key key)
	       (merge-sort result-type (subseq seq mid) pred :key key)
	       pred
	       :key key))))

動作確認

(merge-sort 'list '("Wii" "DS" "PSP" "PS3" "Xbox360") #'string<)
;; => ("DS" "PS3" "PSP" "Wii" "Xbox360")
 
(merge-sort 'list '("Wii" "DS" "PSP" "PS3" "Xbox360") #'char<
              :key #'(lambda (x) (elt x 0)))
;; => ("DS" "PSP" "PS3" "Wii" "Xbox360")