Lispで挿入ソート・その1 - Shammer's Philosophy

挿入ソートというアルゴリズムがあるらしい。

これをLispでやってみようと思う。オリジナルのリストと、ソート済みのリストの双方を用意しなければできなそうだ。流れは以下のような感じだろうか。

オリジナルリストの先頭要素を取得し、ソート済みリストの先頭に追加
オリジナルリストの残りの先頭要素を取得(取得済み要素と呼ぶ)
ソート済みリストの先頭要素と取得済み要素を比較
以下のいずれかを実施
- 取得済み要素の方が大きい場合は、ソート済みリストの次の値を取得し挿入位置を更新、手順3に戻る
- 取得済み要素の方が小さい場合は、ソート済みリストの挿入位置に取得済み要素を追加し、取得済み要素を更新
- ソート済み要素に要素が残っていなければ、取得済み要素をソート済み要素の最後に追加、手順2に戻る

うーむ、、、フローチャートを使わないと書くのが非常に面倒だ。フローチャートを書けばわかりやすいものでも横文字の文章にすると、分岐をうまく表現できずカオスになる。単純に、ある要素をあるリストの特定の条件を満たす場所に入れる、という関数を定義するのが一番最初にすることになるだろうか。難しいのは判定済みの要素をどのように残すか。たとえば、(0 5 10 15 20) とあるところに 13 を入れたいとする。最初に 0 と 13 を比較、13 の方が大きいので、0 はそのままにして 5 と 13 を比較、まだ 13 の方が大きいので 10 と比較、まだ 13 が大きいので 15 と比較、15 の方が大きいので 13 をここに挿入、としたとき、判定済みの 0 と 5 と 10 をどのようにしておくか。単純に、

? (append (cons 13 nil) '(15 20))
(13 15 20)
?

となり、判定済みの (0 5 10) が失われる。これをどのように保持しておくか。。。ここで再帰を使用すれば、この問題は解消できそう。自身を呼出すたびに、残りの判定要素が少なくなっていき、残りの判定要素がなくなったら比較対象要素が最大というようにすればできないだろうか。返り値を、(append (car original-list) (cons target-value nil) (cdr original-list))という感じで連結するようにすればできるはず。

? (defun ins-list (x org)
  (if (null org)
      x
    (let ((y (car org)))
      (if (< x y)
	  (append (cons x nil) org)
	(append (cons (car org) nil) (ins-list x (cdr org)))))))
INS-LIST
? (ins-list 13 '(0 5 10 15 20))
(0 5 10 13 15 20)
?

なんかこれだけのことに結構な時間を要した。これを使って挿入ソートを完成させたいがそれはまた今度。