0

クイックソートに基づくクイック選択、およびカウントソートに基づくカウント選択。

それぞれが、ソートされていない/ソートされたリスト/配列で k 番目に小さい要素を見つけることができます。

ただし、2 つのアルゴリズムのどちらが特定の状況に最も適しているかを判断するための一連のガイドラインを書きたいと思います。状況を考える必要があり、どのアルゴリズムがより適切な選択であるかについてのガイドラインを実装する必要があります。

このために、どのアルゴリズムが特定の領域で特定の強みを持っているかなどを区別するのに少し助けが必要です.

4

1 に答える 1

2

(1)カウント ソートが適切に機能するためには、要素が列挙可能である必要があります (要素から整数への一意のマッピングがあります)。一方、クイックソートでは、2つの要素ごとに明確に定義された比較操作のみが必要です（比較機能は推移的である必要があります-または直感的に-自己矛盾することはありません）。
これは、あなたが直面するべき主要な問題の 1 つです。クイック選択は使用できますが、カウント選択は常に使用できるわけではありません。

なんで？count sortがどのように機能するか、具体的には、個別の要素aと個別の要素の間の順序をどのように決定するかを見てくださいb。整数値を使用して、この種の要素がコレクション内にどのようにあるかをカウントします。wikipeida の記事の疑似コードを見てください。私が言及していることは、次の行で確認できます。

for each input item x:
    Count[key(x)] = Count[key(x)] + 1

値は、要素のkey(x)列挙です-存在しない場合、何がkey(x)得られますか? アルゴリズムはどのように機能しますか？
これは、同じ理由で count select アルゴリズムにも適用されますkey(element)。コレクション内でこの要素が繰り返される回数をカウントするために も使用されます。

(2)もう 1 つの問題は、要素の範囲が膨大な場合の効率です。要素の範囲内で線形であるため、カウントが非効率的です。
クイックソートの実行時間に基づく QuickSelect は、平均して線形ですが、二次時間の複雑さに減衰する場合があります。

(3)もう 1 つの問題はスペースです。カウント選択には、要素の範囲内で線形の追加のスペースが必要ですが、クイック選択では必要ありません。

于 2012-06-02T09:18:28.677 に答える