Algorithms in a Nutshell の 4.4クイックソート(86ページ)

微妙。
参考までに頭を空っぽにして写経してたけど、どうも動かないような気がする。
これが疑似コード。

sort(A)
1. quickSort(A, 0, n-1)
end

quickSort(A, left, right)
1. if (left < right) then
2.   pi = partition(A, left, right)
3.   quickSort(A, left, pi - 1)
4.   quickSort(A, pi + 1, right)
end

partition(A, left, right)
1. p = A[left, right] の中で軸を選ぶ
2. swap A[p] and A[right]
3. store = left
4. for i = left to right - 1 do
5.   if (A[i] <= A[right]) then
6.     swap A[i] and A[store]
7.     store++
8. swap A[store] and A[right]
9. return store
end

partition 関数が範囲の分割をするところをトレースする。
途中は面倒なので省略したけど、省略したところに間違いが潜んでいるに決まってる orz

インデックス

  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16 

初期値

  3   9   6   5   1   9   4   7   4   1   2   0   2   4   1   5   0 
1週目 1.から3. (left=0, right=16, p = 8)

  3   9   6   5   1   9   4   7  [4]  1   2   0   2   4   1   5   0 

      4. (swap A[p] and A[right])

  3   9   6   5   1   9   4   7  [0]  1   2   0   2   4   1   5   4*

      5. から 7. (store=10)

  3   1   4   0   1   2   0   2  [4]  1   9*  6   7   5   9   5   4 

      8. (swap A[store] and A[right])

  3   1   4   0   1   2   0   2  [4]  1   4*  6   7   5   9   5   9*
2週目 1.から3. (left=0, right=9, p = 4)

  3   1   4   0  [1]  2   0   2   4   1   4   6   7   5   9   5   9 

      4. (swap A[p] and A[right])

  3   1   4   0  [1]  2   0   2   4   1*  4   6   7   5   9   5   9 

      5. から 7. (store=4)

  1   0   1   0  [4]* 2   3   2   4   1   4   6   7   5   9   5   9

      8. (swap A[store] and A[right])

  1   0   1   0  [1]* 2   3   2   4   4*  4   6   7   5   9   5   9
... 省略
最後

  1   7   6   1   1   0   0   2   2   4   4   4   3   5   9   5   9

こんなソースになっているので、後で検算しよう。
分かった。select-one が駄目だ。left を加算してない。ということに気付いたので修正。
左端に整列済みを蓄えながら分割する方法はこれまで見たことはなかった。
これはおもしろい。

(define (qsort list cmp-fn)
  (define (swap v a b)
    (if (not (= a b))
        (let ((tmp (vector-ref v a)))
          (vector-set! v a (vector-ref v b))
          (vector-set! v b tmp))))
  (define (select-one l r)
    (+ (floor (/ (- r l) 2)) l))
  (define (partition v l r)
    (let ((p (select-one l r))
          (store l)
          (i l))
      (swap v p r)
      (while (< i r)
             (if (>= (cmp-fn (vector-ref v r) (vector-ref v i)) 0)
                 (begin
                   (swap v i store)
                   (set! store (+ 1 store))))
             (set! i (+ i 1)))
      (swap v store r)
      store))
  (define (inner v left right)
    (if (< left right)
        (let ((pi (partition v left right)))
          (inner v left (- pi 1))
          (inner v (+ pi 1) right))))
  (let ((vec (list->vector list)))
    (inner vec 0 (- (length list) 1))
    (vector->list vec)))

アルゴリズムクイックリファレンス