11

私はクイックソートについて読んでいて、「決定論的クイックソート」と呼ばれることもあることがわかりました。

これは通常のクイックソートの代替バージョンですか？通常のクイックソートと決定論的クイックソートの違いは何ですか？

4

7 に答える 7

13

通常の（「決定論的」）クイックソートは、特定のデータセットでの動作が非常に悪い場合があります（たとえば、最初の並べ替えられていない要素を選択する実装では、既に並べ替えられたデータでO（n ^ 2）時間計算量があります）。

ランダム化されたクイックソート（決定論的に選択するのではなく、ランダムなピボットを選択する）は、すべてのデータセットで期待されるパフォーマンスを向上させるために使用されることがあります。

于 2010-02-22T20:33:46.187 に答える
10

クイックソートはO(n log n)予想/平均時間で実行されますが、O(n^2)最悪の場合です。これは、選択されたピボットが一貫して最小または最大のいずれかである場合に発生します。

理想的には、中央値をピボットとして選択する必要があります。中央値を直接見つけるのにコストがかかりすぎる場合（通常、クイックソートを使用しようとしている場合はこれが当てはまります）、代わりに一般的に行われるのは、3つの潜在的なピボット要素の中央値を取得するか、ピボットとしてランダムな要素を選択することです。 。

後者の方法では、ピボット選択プロセスに固有のランダム性のため、クイックソートが非決定的になります。

于 2010-02-22T20:35:45.823 に答える
4

一般に、ソートアルゴリズムは、要素を毎回まったく同じ順序で一貫してソートする場合、「決定論的」です。id（asc）でソートするレコードのセットが与えられた場合：

  1 Censu
  11 Marju
  4  Cikku
  11 Lonzu

次に、並べ替えアルゴリズムは、Censu、Cikk、Marju、Lonzu、またはCensu、Cikku、Lonzu、Marjuの両方を正しい並べ替えとして返すことができます。決定論的ソートは、常に同じ順序を返すソートです。これは必ずしもそうである必要はありません。クイックソートの場合、ピボットをランダムに選択すると、平均パフォーマンスが速くなります（理想的には中央値を選択しますが、これにはコストがかかる可能性があります）。ただし、これにはコストがかかります。検索はもはや決定論的ではありません。

于 2010-02-22T20:46:21.107 に答える
1

ソースは独自の定義を与えることができます（そしてそうすべきです）が、一般的に決定論的クイックソートは、乱数に依存しない式によってピボットが選択されるものです。たとえば、常に真ん中の要素、常に最初の要素、またはこのようなものを選択します。これは、同じ入力で何度実行しても、パフォーマンスは常に同じになることを意味します（理論的には、実際には違いはそれほど大きくないはずですが）。ランダム化されたクイックソートは、ピボットを選択するときに乱数を使用していることを意味します。つまり、同じ入力での異なる実行のパフォーマンスを（簡単に）予測することはできません。

于 2010-02-22T20:37:05.090 に答える
1

それは分割（またはクイックソートで使用される有名な分割統治法からの分割ステップ）と関係があります。最後（または任意の位置の最初の要素または要素、データセットが分割されるたびに同じ位置である必要がある）がパーティション化のピボットとして使用されるたびに、それは決定論的クイックソートです。ピボットがランダムに選択された場合、それはランダム化されたクイックソートです。

これはそれを横切る講義ノートです。

お役に立てば幸いです

乾杯

于 2010-02-22T20:37:29.253 に答える
1

クイックソートの前にある一般的な形容詞は、決定論的でランダム化されています。決定論的とは、クイックソートが常に同じデータセットを同じ方法で並べ替えるのに対し、ランダム化されたクイックソートはランダム化を使用し、同じデータをまったく同じ方法で並べ替えることはめったにないことを意味します（データセットが非常に小さい場合を除いて、より一般的です） 。

決定論的

それは、ピボットがどのように選択されるかにかかっています。決定論的クイックソートでは、ピボットは、最初、最後、または中間の要素などの同じ相対インデックスで常にピボットを選択するか、任意の数の所定の要素の選択の中央値を使用して選択されます。たとえば、一般的な方法は、最初、最後、および中間の要素の中央値をピボットとして選択することです。今説明した中央値3の方法でも、特定のデータセットはO（N ^ 2）の時間計算量を簡単に与えることができます。データセットの例は、いわゆるオルガンパイプのデータセットです。

array = [1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2,1]

ランダム化

ランダム化されたクイックソートは、ランダムピボットのみを選択することも、ランダムに選択されたピボットの中央値を使用することもできます。O（N ^ 2）の時間計算量の可能性はまだありますが、確率ははるかに小さく、データセットのサイズが大きくなるにつれて小さくなります。

于 2010-02-22T21:03:44.550 に答える
0

決定論的クイックソートがどのように実装され、非決定論的クイックソートがどのように実装されているかについて他の多くの人がすでにあなたに言ったことに加えて、そのようなソートのはるかに重要な側面の1つは、決定論的クイックソートでは常に同じ順序であると信じていますキーが衝突したときに記録しますが、非決定論的なクイックソートでは、ソートを実行するたびにそのようなレコードの順序が異なる場合があります。

一意でないキーがある場合は、非決定論的なクイックソートを使用しないでください。

于 2010-02-22T20:49:03.023 に答える