読者です 読者をやめる 読者になる 読者になる

コムソート

common lisp algorithm

llvmチュートリアルの続きを読もうと思ったら、今はドキュメント関連のページがエラーで見れなくなっていたので、代わりに前から少し気になっていたコムソートを実装してみることにする。
参考サイト: コムソート - Wikipedia(最終更新 2009年11月29日 (日) 04:52)
参照: nlet

;;; バブルソートの改良版
;;;  バブルソートが隣接する要素同士でのみ比較/交換を行うのに対して、
;;;  コムソートは最初大きな間隔で要素同士の比較/交換を行い、徐々にその間隔を狭めていく(最終的には、間隔=1となりバブルソートと等しくなる)

;; 次の間隔を求める
(defun next-h (h)
  (max 1 (floor h 1.3)))

(defun comb-sort (ary &aux (len (length ary)))
  (nlet self ((h (next-h len)))
    (let ((ordered? (= 1 h)))  ; 間隔(h)が1の場合は、既に整列されている可能性がある
      (dotimes (i (- len h))
        (when (> #1=(aref ary i) #2=(aref ary (+ i h)))
          (rotatef #1# #2#)
          (setf ordered? nil)))
      (if ordered?
          ary
        (self (next-h h))))))
#|
;; 改良版
(defun next-h (h)
  (let ((h (floor h 1.3)))
    (case h
      ((0)        1)
      ((9 10)    11)   ; h(間隔)が9か10の場合は、11を返す
      (otherwise h))))
|#
> (defparameter *ary* (coerce (loop REPEAT 100 COLLECT (random 1000)) 'vector))
--> *ARY*

> *ary*
--> #(347 590 124 258 90 451 969 792 819 989 818 349 312 920 275 304 627 81 991 654
      360 524 554 886 770 792 691 911 828 467 233 848 985 576 362 126 564 284 758
      743 214 243 205 152 799 390 565 28 449 987 391 368 70 557 88 831 890 429 82 8
      260 577 691 248 678 818 459 972 746 904 998 150 589 322 205 173 904 839 131
      341 634 134 145 626 804 58 193 148 203 938 178 546 111 689 671 324 169 588
      327 33)

> (comb-sort *ary*)
--> #(8 28 33 58 70 81 82 88 90 111 124 126 131 134 145 148 150 152 169 173 178 193
      203 205 205 214 233 243 248 258 260 275 284 304 312 322 324 327 341 347 349
      360 362 368 390 391 429 449 451 459 467 524 546 554 557 564 565 576 577 588
      589 590 626 627 634 654 671 678 689 691 691 743 746 758 770 792 792 799 804
      818 818 819 828 831 839 848 886 890 904 904 911 920 938 969 972 985 987 989
      991 998)

思っていたよりずっと簡単だった。
シェルソートもそうだが、もともとのアルゴリズムとほとんど変わらないのに、比較/交換の間隔を広げるだけで性能が劇的に良くなる*1(バブルソートの場合、O(n^2) ==> O(n^log n))というのは面白い。

0〜9999までの値がランダムに並んだ配列に対して、コムソートを適用した結果の図。
タイトルは"comb-sort [selfの呼び出し回数+1 : h]"形式。
確か、x軸が配列の添字値で、y軸が要素の値。
クイックソートなどとは違い、全体が徐々に収束していっているのが分かる。

*1:ただし、整列済みの入力対する処理速度は、(最後に交換した位置を覚えておくように修正した)バブルソートの方が速そう。上の実装のコムソートの場合、どのような入力に対しても、最低でもおよそ(* N (log N 1.3)#|= hが1になるまでのself呼出回数|#)回の要素比較が必要になるはずなので。