コムソート
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軸が要素の値。
クイックソートなどとは違い、全体が徐々に収束していっているのが分かる。
