5

これは非常に一般的な本 (Cormen、Leiserson、Rivest、Stein) のように思われるので、誰かが助けてくれることを願っています。第 8 章では、並べ替えを数えるためのアルゴリズムが示されています。入力配列 A がどこにあり、配列 C のサイズが 0 から k までの範囲かがわかります。C[i] は、i に等しい A の要素数を含むように作成されます。例えば：

A: [2,5,3,0,2,3,0,3]
C: [2,0,2,3,0,1]

しかし、この後、彼らは C[i] が i 以下の要素数を含むようにします。例えば：

C: [2,2,4,7,7,8]

なぜこれが必要なのですか？元の C を反復処理して、そこから並べ替えられた配列を作成することはできませんか? 各数値の正確な数を知っているので、B に各数値の適切な量を順番に入れ、並べ替えられた配列を作成できます。C を最初の形式から 2 番目の形式に変換すると、どういうわけか安定しますか?

4

1 に答える 1

4

私はあなたが中間体で次のことをすることを提案していると思いますC（インデックス1配列を使用して）：

i = 1
for k = 1 to len(C)
  for j = 1 to C[i]
    B[i] = k
    i = i + 1

これは合理的であるように思われ、同じ漸近的な実行時間があります。ただし、並べ替えるキーを持つアイテムが単一の整数だけでなく、他のデータが添付されている場合を考えてみてください。カウントアルゴリズムにより、ソートが安定します。同じキーを持つアイテムの相対的な順序は保持されます（ウィキペディアの記事を参照）。のインデックスからの出力を割り当てるだけでは、一般的なデータを並べ替えることができなくなりますC。したがって、ソートが。を介して要素を割り当てる理由B[C[A[j]]] <- A[j]。

好奇心旺盛な人のために、これは元のアルゴリズムの完成です：

# C[i] now contains the number of elements equal to i.
for i = 1 to k
  C[i] <- C[i] + C[i-1]
# C[i] now contains the number of elements less than or equal to i.
for j = length[A] downto 1
  B[C[A[j]]] <- A[j]
  C[A[j]] <- C[A[j]] - 1

最後の部分のデクリメントを説明するために、この本を引用します。この本は、この種の安定性についても説明しています。

要素が明確でない可能性があるため、配列に値をC[A[j]]配置するたびにデクリメントします。デクリメントすると、値が存在する場合はそれに等しい次の入力要素が、出力配列の直前の位置に移動します。A[j]BC[A[j]]A[j]A[j]

COUNTING-SORTまた、そうすると、入力配列内の特定のアイテムよりも少ないアイテムの数がカウントされないため、これを呼び出すことができなくなると思います（定義されているとおり）。:)

于 2013-02-21T06:16:41.617 に答える