クイックソート：ピボットの選択

StackOverflow https://stackoverflow.com/questions/164163

質問

Quicksortを実装するとき、やらなければならないことの1つは、ピボットを選択することです。しかし、以下のような擬似コードを見ると、ピボットをどのように選択するかが明確ではありません。リストの最初の要素？他に何か？

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1  
         return array  
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

ピボットを選択する概念と、異なるシナリオが異なる戦略を必要とするかどうかを把握するのを手伝ってくれますか。

役に立ちましたか？

解決

ランダムピボットを選択すると、最悪の場合のO（n 2 ）パフォーマンスに遭遇する可能性が最小限に抑えられます（常に最初または最後を選択すると、ほぼソートまたはほぼ逆の場合に最悪のパフォーマンスが発生します）ソートされたデータ）。ほとんどの場合、中間要素を選択することもできます。

また、これを自分で実装する場合、インプレースで機能するアルゴリズムのバージョンがあります（つまり、2つの新しいリストを作成してから連結することはありません）。

他のヒント

要件によって異なります。ピボットをランダムに選択すると、O（N ^ 2）パフォーマンスを生成するデータセットを作成するのが難しくなります。 「中央値3」（最初、最後、中間）も問題を回避する方法です。ただし、比較の相対的なパフォーマンスに注意してください。比較にコストがかかる場合、Mo3はランダムに（単一のピボット値）を選択するよりも多くの比較を行います。データベースレコードは、比較するとコストがかかる場合があります。

更新：コメントを回答に追加。

mdkess アサート：

  

「中央値3」は最初の最後の中間ではありません。 3つのランダムインデックスを選択し、この中間値を取ります。全体のポイントは、ピボットの選択が決定論的でないことを確認することです-そうであれば、最悪の場合のデータは非常に簡単に生成できます。

返信先：

  • Median-Ofを使用したHoareの検索アルゴリズムの分析-3つのパーティション（1997） P Kirschenhofer、H Prodinger、C Mart＆＃237; nezがあなたの主張を支持しています（「3つの中央値」は3つのランダムなアイテムです）。

  • portalに記事があります。 .acm.org は、Hannu Erki＆＃246;による「3つのメディアンの最悪の並べ替え」に関するもので、The Computer Journal、Vol 27、No 3、1984に掲載されています。 -26：記事のテキストを取得しました。セクション2 'アルゴリズム'の開始： ' A [L：R]の最初、中間、および最後の要素の中央値を使用することにより、ほとんどの実際的な状況で効率的にかなり等しいサイズの部分に分割できます。 'したがって、最初から最後までのMo3アプローチについて議論しています。]

  • 興味深い別の短い記事はMD McIlroyによるもので、＆quot; A Software-Practice and Experience、Vol。に掲載されているQuicksortのKiller Adversary＆quot; 29（0）、1＆＃8211; 4（0 1999）。ほとんどすべてのQuicksortを二次的に動作させる方法を説明しています。

  • AT＆amp; T Bell Labs Tech Journal、1984年10月「作業ソートルーチンの構築における理論と実践」州＆quot; Hoareは、ランダムに選択された複数の行の中央値を分割することを提案しました。 Sedgewick [...]は、最初の[...]最後の[...]および中間の中央値を選択することをお勧めします。これは、「3の中央値」の両方の手法が文献で知られていることを示しています。 （2014-11-23更新：この記事は、で入手できるようです。 IEEE Xplore または Wiley から＆＃8212;メンバーシップを持っている場合、または料金を支払う準備ができている場合）

  • 「並べ替え関数のエンジニアリング」 JL BentleyとMD McIlroyによる、Software Practice and Experience、Vol 23（11）、1993年11月に公開された、彼らは問題の広範な議論に入り、彼らはデータのサイズに部分的に基づいて適応分割アルゴリズムを選択しましたセット。さまざまなアプローチのトレードオフについて多くの議論があります。

  • 「median-of-three」のGoogle検索は、さらに追跡するのに非常に有効です。

情報をありがとう。以前、決定論的な「3の中央値」にしか遭遇していませんでした。

はい、このクラスを教えたばかりです。

いくつかのオプションがあります。
シンプル：範囲の最初または最後の要素を選択します。 （部分的にソートされた入力では悪い） より良い：範囲の中央のアイテムを選択します。 （部分的にソートされた入力の方が良い）

ただし、任意の要素を選択すると、サイズnの配列がサイズ1とn-1の2つの配列にうまく分割されないリスクがあります。それを十分に頻繁に行うと、クイックソートはO（n ^ 2）になるリスクを負います。

私が見た改善の1つは、中央値（最初、最後、中）を選択することです。 最悪の場合でも、O（n ^ 2）に到達する可能性がありますが、確率的には、これはまれなケースです。

ほとんどのデータでは、最初または最後を選択するだけで十分です。ただし、最悪のシナリオ（部分的に並べ替えられた入力）に頻繁に遭遇する場合、最初のオプションは中心値を選択することです（これは、部分的に並べ替えられたデータの統計的に適切なピボットです）。

まだ問題が発生している場合は、中央分離帯に進みます。

固定ピボットを選択することは決してありません-これを攻撃して、アルゴリズムの最悪の場合のO（n ^ 2）ランタイムを悪用することができます。パーティション分割の結果、1つの要素の1つの配列とn-1個の要素の1つの配列が生じると、Quicksortの最悪のランタイムが発生します。最初の要素をパーティションとして選択するとします。誰かがアルゴリズムを降順で配列にフィードすると、最初のピボットが最大になるため、配列内の他のすべてがその左側に移動します。その後、再帰すると、最初の要素が再び最大になります。そのため、もう一度すべてを左に配置する、というようになります。

より良い方法は、中央値3の方法です。この方法では、3つの要素をランダムに選択し、中央を選択します。選択した要素は最初または最後ではないことを知っていますが、中心極限定理により、中間要素の分布は正規になります。つまり、中間に向かう傾向があります（したがって、 、n lg n時間）。

アルゴリズムのO（nlgn）ランタイムを絶対に保証したい場合、配列の中央値を見つける5列の方法はO（n）時間で実行されます。これは、最悪の場合は、T（n）= O（n）（中央値を見つける）+ O（n）（パーティション）+ 2T（n / 2）（左右に再帰）です。マスター定理により、これはO（n lg n）。ただし、一定の要因は非常に大きく、最悪の場合のパフォーマンスが主な関心事である場合は、代わりにマージソートを使用します。マージソートは、平均でクイックソートよりも少し遅く、O（nlgn）時間を保証します（そして、はるかに高速になります）このラメ中央値クイックソートより）。

Median of Mediansアルゴリズムの説明

あまりにも賢くなりすぎて、ピボット戦略を組み合わせようとしないでください。最初、最後、および中央のランダムインデックスの中央値を選択することにより、3の中央値とランダムピボットを組み合わせた場合、3次の中央値を送信する多くの分布に対して脆弱です（したがって、実際にはプレーンランダムピボット）

たとえば、パイプオルガン分布（1,2,3 ... N / 2..3,2,1）の最初と最後は両方とも1で、ランダムインデックスは1より大きい数になり、中央値は1（最初または最後のいずれか）を選択すると、非常に不均衡なパーティションが作成されます。

これは、データの最初のソート方法に完全に依存しています。擬似ランダムと思われる場合は、ランダムに選択するか、中央を選択するのが最善の策です。

ランダムにアクセス可能なコレクション（配列など）を並べ替える場合、物理的な中央のアイテムを選択するのが一般的に最善です。これにより、配列がすべてソート済み（またはほぼソート済み）である場合、2つのパーティションはほぼ均等になり、最高の速度が得られます。

線形アクセスのみ（リンクリストなど）で並べ替える場合は、最初のアイテムを選択するのが最善です。これは、アクセスが最も速いアイテムだからです。ただし、ここでリストが既に並べ替えられている場合は、混乱します。一方のパーティションは常にnullになり、もう一方のパーティションにはすべてがあり、最悪の時間を生成します。

ただし、リンクリストの場合、最初のリスト以外のものを選択すると、事態はさらに悪化します。リストされたリストの中央のアイテムを選択し、各パーティションステップでそれをステップスルーする必要があります-logN回行われる合計時間O（1.5 N * log N）を行うO（N / 2）操作を追加しますそして、それは、開始する前にリストがどれくらいの長さかを知っている場合です-通常はそうではないので、それらを数えるために最後まで歩き、それから途中まで歩んで真ん中を見つけてから、 3回目の実際のパーティション：O（2.5N * log N）

クイックソートをこれを行う3つのセクションに分けるのが簡単です

  1. データ要素関数の交換または交換
  2. パーティション関数
  3. パーティションの処理

1つの長い関数よりもわずかに非効率的ですが、理解しやすいものです。

コードは次のとおりです。

/* This selects what the data type in the array to be sorted is */

#define DATATYPE long

/* This is the swap function .. your job is to swap data in x & y .. how depends on
data type .. the example works for normal numerical data types .. like long I chose
above */

void swap (DATATYPE *x, DATATYPE *y){  
  DATATYPE Temp;

  Temp = *x;        // Hold current x value
  *x = *y;          // Transfer y to x
  *y = Temp;        // Set y to the held old x value
};


/* This is the partition code */

int partition (DATATYPE list[], int l, int h){

  int i;
  int p;          // pivot element index
  int firsthigh;  // divider position for pivot element

  // Random pivot example shown for median   p = (l+h)/2 would be used
  p = l + (short)(rand() % (int)(h - l + 1)); // Random partition point

  swap(&list[p], &list[h]);                   // Swap the values
  firsthigh = l;                                  // Hold first high value
  for (i = l; i < h; i++)
    if(list[i] < list[h]) {                 // Value at i is less than h
      swap(&list[i], &list[firsthigh]);   // So swap the value
      firsthigh++;                        // Incement first high
    }
  swap(&list[h], &list[firsthigh]);           // Swap h and first high values
  return(firsthigh);                          // Return first high
};



/* Finally the body sort */

void quicksort(DATATYPE list[], int l, int h){

  int p;                                      // index of partition 
  if ((h - l) > 0) {
    p = partition(list, l, h);              // Partition list 
    quicksort(list, l, p - 1);        // Sort lower partion
    quicksort(list, p + 1, h);              // Sort upper partition
  };
};

理想的には、ピボットは配列全体の中央の値である必要があります。 これにより、最悪の場合のパフォーマンスが得られる可能性が低くなります。

クイックソートの複雑さは、ピボット値の選択によって大きく異なります。たとえば、常に最初の要素をピボットとして選択すると、アルゴリズムの複雑さはO（n ^ 2）と同じくらい最悪になります。ピボット要素を選択するスマートな方法があります- 1.配列の最初、中間、最後の要素を選択します。 2.これらの3つの数値を比較して、1より大きく、他の数値よりも小さい数値、つまり中央値を見つけます。 3.この要素をピボット要素として作成します。

この方法でピボットを選択すると、配列がほぼ半分に分割されるため、複雑さが増します。 O（nlog（n））になります。

平均して、中央値3は小さいnに適しています。 nが大きいほど、中央値5が少し良くなります。 9番目の値は、「3の中央値の中央値」です。 nが非常に大きい場合はさらに優れています。

サンプリングを行うほど、nが大きくなるほど良くなりますが、サンプルを増やすと改善は劇的に遅くなります。また、サンプルのサンプリングとソートのオーバーヘッドが発生します。

簡単に計算できるため、中間インデックスの使用をお勧めします。

丸めて計算できます（array.length / 2）。

真に最適化された実装では、ピボットを選択する方法は配列サイズに依存する必要があります-大きな配列の場合、良いピボットを選択するためにより多くの時間を費やすことができます。完全な分析を行わずに、「O（log（n））要素の中央」を推測します。良い出発点であり、これには追加のメモリを必要としないという追加のボーナスがあります：大きいパーティションでテールコールを使用し、インプレースパーティショニングを使用して、ほぼすべての段階で同じO（log（n））の追加メモリを使用しますアルゴリズム。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top