1

既にランダムな配列を取得しているのに、なぜランダム化されたクイック ソートを使用するのでしょうか?

ランダムな配列を受け取り、最後のエントリを毎回ピボットとして選択した場合でも、各エントリの配置場所さえわからないランダムな配列を受け取ったので、それはまだランダムと見なされません。

通常のクイックソートの疑似コード

QUICKSORT(A,p,r)
if p< r
     q = PARTITION(A,p,r)
     QUICKSORT(A,p,q-1)
     QUICKSORT(A,q+1,r)

PARTITION(A, p, r)
x = A[r]
i = p − 1
for j = p to r − 1 do
     if A[j] ≤ x then
          i = i + 1
          exchange A[i] and A[j]

exchange A[i + 1] and A[r]
return i + 1

ランダム化されたクイックソートの疑似コード

RandPartition(A, p, r)
     i = Random(p, r)
     exchange A[r] and A[i]
     return PARTITION(A, p, r)

RandQuicksort(A, p, r)
     if p < r then
     q = RandPartition(A, p, r)
     RandQuicksort(A, p, q − 1)
     RandQuicksort(A, q + 1, r)
4

1 に答える 1

1

はい、入力がランダム化されていることがわかっている場合、追加のランダム化は何の役にも立ちません。ピボットとして最後の要素を決定論的に選択することも同様に良いでしょう。

入力がランダム化されることがわかっていない場合、状況はまったく異なります。

于 2013-11-01T22:25:23.083 に答える