マージソートin LISP
資格試験の勉強中マージソートの問題が出たのでLISPで書いてみた。
アルゴリズムはWikipediaを見てくだせえ
マージソート - Wikipedia
とりあえずソースはこんな感じ
(defun marge (lis1 lis2) (if (null lis1) lis2 (if (null lis2) lis1 (let ((top1 (first lis1)) (top2 (first lis2)) (tail1 (rest lis1)) (tail2 (rest lis2))) (if (< top1 top2) (cons top1 (marge tail1 lis2)) (cons top2 (marge lis1 tail2))) ) ) ) ) (defun get-list (lis n) (if (or (<= n 0) (null lis)) nil (cons (first lis) (get-list (rest lis) (- n 1))) ) ) (defun half-list (lis f) (if f (get-list lis (floor (/ (length lis) 2)) ) (reverse (get-list (reverse lis) (ceiling (/ (length lis) 2)))) ) ) (defun marge-sort (lis) (if (= 1 (length lis)) lis (let ((lis1 (half-list lis t)) (lis2 (half-list lis nil))) (marge (marge-sort lis1) (marge-sort lis2))) ) )
各関数の説明をすると
- marge(lis1 lis2):リストlis1とリストlis2を整列させて結合させる
- get-list(lis n):リストlisの先頭からn番目までのリストを取ってくる
- half-list(lis f):fが真ならリストlisの前半分を、偽なら後ろ半分を取ってくる
- marge-sort(lis): マージソートする
実行結果はこれ
CL-USER> (setf lis (list 2 3 5 1 2 4 7 8 4 6 7 9)) (2 3 5 1 2 4 7 8 4 6 7 9) CL-USER> (marge-sort lis) (1 2 2 3 4 4 5 6 7 7 8 9)
昨日に比べてエラーも少なくすんなりかけた。けどもう少しスッキリしたコードを書きたい(特にmarge)。
あとクセでLispは「(関数名 引数)」なのに「関数名(引数)」と良く書いてしまう…
何も見ずに我ながらよくやったと思う。LISPに少し慣れてきた