クイックソートの内部ループ

クイックソートの内部ループには(自分が知っている限りでは)二種類あるな、とふと思ったので、思い出して書いてみた。

;;; 補助マクロ/関数
;; whileループ
(defmacro while (exp &body body)
  `(loop WHILE ,exp 
         DO (locally ,@body)))

;; 配列をシャッフル
(defun shuffle (ary)
  (loop REPEAT 2 DO
    (loop FOR i FROM 0 BELOW (length ary)
      DO
      (rotatef (aref ary i) (aref ary (random (length ary))))))
  ary)

;;; クイックソート１
;;; 内部ループ:
;;;  - 配列の前方と後方から不正な要素を探して、見つかった場合は互いを交換する、ということを繰り返す
(defun qsort1 (ary &optional (beg 0) (end (length ary)))
  (if (not (< beg end))
      ary
    (macrolet ((ref (i) `(aref ary ,i)))
      (let ((pivot (ref beg))
            (lt beg)
            (gt end))
        ;; pivotより小さい要素は前方に、大きい要素は後方にまとめる
        (loop
         (while (and (< lt gt) (< pivot (ref (decf gt))))) ; pivotより大きくない要素を後ろから探す
         (while (and (< lt gt) (< (ref (incf lt)) pivot))) ; pivotより小さくない要素を前から探す
         (unless (< lt gt)
           (return))
         (rotatef (ref lt) (ref gt))) ; 位置が正しくない要素同士を互いに入れ替え
        ;; pivotを区分点に配置する
        (rotatef (ref beg) (ref lt))
        (qsort1 ary beg lt)      ; pivotより小さな要素に対して再帰 ※ (<= x pivot)
        (qsort1 ary (1+ lt) end))))) ; pivotより大きな要素に対して再帰 ※ (>= x pivot)

;;; クイックソート２
;;; 内部ループ:
;;;  - 配列を走査して、ピボット要素より小さい要素を全て前方に移動する
(defun qsort2 (ary &optional (beg 0) (end (length ary)))
  (if (not (< beg end))
      ary
    (macrolet ((ref (i) `(aref ary ,i)))
      (let ((pivot (ref beg))
            (border beg))
        ;; pivotよりも小さい要素を先頭に寄せる
        (loop FOR i FROM (1+ beg) BELOW end 
              WHEN (< (ref i) pivot)
          DO 
          (rotatef (ref (incf border)) (ref i)))
        ;; pivotを区分点に配置する
        (rotatef (ref beg) (ref border)) 
        (qsort2 ary beg border)          ; pivotより小さい要素に対して再帰 ※ (<  x pivot)
        (qsort2 ary (1+ border) end))))) ; pivotより大きい要素に対して再帰 ※ (>= x pivot)

;;; 実行

(qsort1 #(83 892 477 71 49 9 38 9 24824 2))
--> #(2 9 9 38 49 71 83 477 892 24824)

(qsort2 #(83 892 477 71 49 9 38 9 24824 2))
--> #(2 9 9 38 49 71 83 477 892 24824)

;; 十万個の数値列
(defparameter *nums* 
  (shuffle (coerce (loop REPEAT 100000 COLLECT (random 10000000)) 'vector)))

(subseq *nums* 0 10)
--> #(2443505 1429801 8480951 3631955 8952550 8437039 6684043 2441681 1467244 8810784)

(subseq (qsort1 (copy-seq *nums*)) 0 10)
--> #(231 275 336 339 355 396 473 479 975 1143)

(time
  (length (qsort1 (copy-seq *nums*))))
Evaluation took:
  0.113 seconds of real time
  0.112007 seconds of total run time (0.112007 user, 0.000000 system)
  99.12% CPU
  226,319,370 processor cycles
  400,008 bytes consed
--> 100000

(time
  (length (qsort2 (copy-seq *nums*))))
Evaluation took:
  0.154 seconds of real time
  0.156010 seconds of total run time (0.156010 user, 0.000000 system)
  101.30% CPU
  307,169,274 processor cycles
  400,008 bytes consed
--> 100000

この場合qsort1の方が高速。
ぱっと見た感じでは、qsort1とqsort2では要素の比較回数はほぼ同じ*1。
ただ、qsort2の場合、配列の要素の並びがどうあれピボット要素よりも小さい要素の数だけ交換が発生するけど、qsort1では正しくない位置にある要素分だけを交換するので、qsort1の方が速くなっているのかも。

*1:各関数呼び出しの内部ループでは、どちらも(- end beg 1)。ただし、両者ではpivotの両端に分ける要素の基準が若干異なるため、重複要素を含むような配列では再帰過程に若干差異が生じ、結果として全体の比較回数も違ってくる(と思う)。