Lispでバブルソート

Lisp で乱数リストを作る - Shammerismの続き第一段。まずはバブルソートから。一番最初の値と次の値を比較して、大きい方を後ろにひたすらずらしていき、最後まで行けば自動的に一番大きいものは最後になる、というやり方。

(defun bubble-sort (l)
  (labels ((compare (n l)
		    (if (null l)
			n
		      (compare (max n (car l)) (cdr l)))))
    (format t "~A~%" l)
    (if (null l)
	nil
      (let (last-element)
	(setf last-element (compare (car l) (cdr l)))
	(format t "last-element is ~A~%" last-element)
	(append (bubble-sort (remove last-element l)) (list last-element))))))

再帰で書くと逆にわかりにくいかも。流れとしては、

1. 元リストの(car l)-オリジナルリストの先頭要素-と(cdr l)-オリジナルリストの残り要素-をcompareに渡す
2. オリジナルリストの先頭要素と、オリジナルリストの残り要素の先頭要素を比較して大きい方を残す
3. この残った大きい方と、さらに残り要素の先頭の大きい方と比較して大きい方だけを残す
4. 残り要素がなくなるまでこれを繰り返し、一番最後まで残った大きい値を返す(compare の戻り値)
5. オリジナルリストから最大値を除外したリストを引数に自身を再帰的に呼出した結果と、既に特定された要素内の最大要素を連結

という流れになる。自身を呼出すたびに最大値とそれ以外の要素が特定され、それ以外の要素がなくなった時点でソート完了となる。実行例は以下。

? (bubble-sort (get-random-list 10))
(45 22 11 93 82 20 2 4 72 52)
last-element is 93
(45 22 11 82 20 2 4 72 52)
last-element is 82
(45 22 11 20 2 4 72 52)
last-element is 72
(45 22 11 20 2 4 52)
last-element is 52
(45 22 11 20 2 4)
last-element is 45
(22 11 20 2 4)
last-element is 22
(11 20 2 4)
last-element is 20
(11 2 4)
last-element is 11
(2 4)
last-element is 4
(2)
last-element is 2
NIL
(2 4 11 20 22 45 52 72 82 93)
? 

last-elementには、毎回その時点の最大値が入っており、それが要素の一番最後に追加されている。