バブルソート作った (Common Lisp)

やっとバブルソートが出来たので上げる。

上のサイトとほぼ一緒になってしまったorz。変えたところはletの変数を増やしたところと、出力をするようにしたところ、変数名を変えたところかなと。なんとか再帰で出来ないんだろうか...。

ソースコード

(defun do-bubble (lst)
  (if (cdr lst)
      (let ((l1 (car lst)) (l2 (car (cdr lst))))
	(if (> l1 l2)
	    (setf (car lst) l2
		  (car (cdr lst)) l1))
	(setf (cdr lst) (do-bubble (cdr lst)))))
  lst)

(defun bubble (lst)
  (let ((result) (lst0 lst))
    (dotimes (x (length lst0) result) ;;0からリストの長さ分(n-1)繰り返す
      (setf lst0 (do-bubble lst0))  ;;バブルソートをする
      (format t "(~{~A ~})~%" lst0)
      (setf result (append (list (car (reverse lst0))) result))
      (setf lst0 (reverse (cdr (reverse lst0)))));反転して、また反転する
    result)) ;;結果を返す

実行イメージ
一回目
(3 1 4 6 2 5)
(1 3 4 6 2 5)
(1 3 4 6 2 5)
(1 3 4 6 2 5)
(1 3 4 2 6 5)
(1 3 4 2 5 6)

実行のやり方
(bubble '(3 1 4 6 2 5))

実行結果

(bubble '(3 1 4 6 2 5))
(1 3 4 2 5 6 )
(1 3 2 4 5 )
(1 2 3 4 )
(1 2 3 )
(1 2 )
(1 )
=>(1 2 3 4 5 6)

解説

ちょっとだけコードの解説

(setf result (append (list (car (reverse lst0))) result))

バブルソートしたリストを反転させて、反転したリストの第一要素(car)を取り出し、
取り出したものをresultにappendする。そしてappendしたものは、resultに代入される。

(setf lst0 (reverse (cdr (reverse lst0)))))

反転してしたリストの第二要素以降(cdr)を取り出す。取り出したリストを
また反転してもとに戻すとあら不思議、最後の要素を除いたリストが出来ました。

感想

リストリスト操作のテクニックが二つあったのが発見だった。

(append (list (car (reverse lst0))) result)

(reverse (cdr (reverse lst0)

この最後の要素を取り出してリストにするテクニックと、最後の要素を取り除くテクニックは覚えておきたいなと思う。