この頁では

(my_sort リスト)

として,引数のリストの要素を昇順にソートしたリストを返す関数を作成することで,Lispプログラミングに慣れることを目標にする.

my_sort関数をクィックソートで実装すると以下のようになる.

;; 引数のリストの要素をクィックソートする
(defun my_sort (x)
  ;; 基底.引数リストの要素数が1ならそのまま返す
  (if (eql (length x) 1)
      x
    ;; 基底.引数リストの要素数が2ならソートして返す
    (if (eql (length x) 2)
	(if (< (first x) (second x))
	    (list (first x) (second x))
	  (list (second x) (first x)))
      ;; 基底以外.
      ;; 引数リストの最初の要素をピボットにする.
      (let ((pibot (car x))
	    (bigger nil)
	    (smaller nil))
	;; 引数リストの要素をピボットより小さいリスト(smaller)と大きいリスト(bigger)に分ける
	(dolist (a (cdr x))
	  (if (< pibot a)
	      (if (not (listp bigger))
		  (setf bigger (list bigger a))
		(setf bigger (append bigger (list a))))
	    (if (not (listp smaller))
		(setf smaller (list smaller a))
	      (setf smaller (append smaller (list a))))))
	;; smallerとbiggerの要素数が1以上なら再帰呼び出し.
	(if (not (null smaller))
	    (setf smaller (my_sort smaller)))
	(if (not (null bigger))
	    (setf bigger (my_sort bigger)))
	;; 最後にソート済みsmaller,biggerとピボットをくっつける
	(append smaller (list pibot) bigger)))))

;; ドライバ
(let ((inputlists '((5 6 4 10 7 9 1) (9 8 7 6 5 4 3 2 1) (1 2 3 4 5 6 7 8 9) (1) (1 2) (1 2 3))))
  (dolist (inputlist inputlists)
    (format t "inputlist = ~A~%" inputlist)
    (format t "sortedlist = ~A~%~%" (my_sort inputlist))))

ちょっと長くなった.以下に実行結果を示す.

$ clisp my_sort1.lisp
inputlist = (5 6 4 10 7 9 1)
sortedlist = (1 4 5 6 7 9 10)

inputlist = (9 8 7 6 5 4 3 2 1)
sortedlist = (1 2 3 4 5 6 7 8 9)

inputlist = (1 2 3 4 5 6 7 8 9)
sortedlist = (1 2 3 4 5 6 7 8 9)

inputlist = (1)
sortedlist = (1)

inputlist = (1 2)
sortedlist = (1 2)

inputlist = (1 2 3)
sortedlist = (1 2 3)

変数がどういう状況でリストで,どういう状況ならアトムなのかよくわかっていない.今後の課題.ここで初登場のappendは引数のリストを結合したリストを作成する.

> (append '(1) '(2))
> (1 2)

続く.