2

Robert Sedwickによるアルゴリズムブックのクイックソートセクションからのテキストに続きます。

配列の左、中央、右から 3 つの要素を選択することで、センチネルをこのスキームに組み込むことができます。3 つの要素を並べ替え、真ん中の 1 つを で交換しa[r-1]、 で分割アルゴリズムを実行しa[l+1],...,a[r-2]ます。この改善は、3 つの方法の中央値と呼ばれます。

3 つの方法の中央値は、3 つの方法ですばやく並べ替えるのに役立ちます。

  1. これにより、実際の並べ替えで最悪のケースが発生する可能性がはるかに低くなります。並べ替えにO(N^2)時間がかかるようにするには、検査される 3 つの要素のうち 2 つがファイル内の最大または最小の要素に含まれている必要があり、このイベントはほとんどのパーティションで一貫して発生する必要があります。

  2. この機能は、パーティション分割の前に検査される 3 つの要素の 1 つによって提供されるため、パーティション分割のためのセンチネル キーが不要になります。

  3. これにより、アルゴリズムの合計平均実行時間が約 5% 短縮されます。

    template <class Item> 
void exch(Item &A, Item &B) 
      { Item t = A; A = B; B = t; } 

template <class Item> 
void compexch(Item &A, Item &B) 
      { if (B < A) exch(A, B); }

static const int M = 10;
template <class Item>
void quicksort(Item a[], int l, int r)
  {
    if (r-l <= M) return;
    exch(a[(l+r)/2], a[r-1]);  // line 1
    compexch(a[l], a[r-1]);   // line 2.
    compexch(a[l], a[r]);     // line 3.
    compexch(a[r-1], a[r]);   // line 4.
    int i = partition(a, l+1, r-1);
    quicksort(a, l, i-1);
    quicksort(a, i+1, r);
  }

template <class Item>
void hybridsort(Item a[], int l, int r)
  { quicksort(a, l, r); insertion(a, l, r); }

上記のテキストに関する私の質問、誰でも簡単な例で説明できますか

  1. 作者が「最悪の場合、実際の並べ替えで発生する可能性ははるかに低い。並べ替えに N 平方時間かかる場合、検査された 3 つの要素のうち 2 つが最大のものでなければならない」とはどういう意味ですか?

  2. 「パーティショニング用のセンチネル キーが不要になる」とはどういう意味ですか?

  3. 上記のプログラムでは、上記のコードでコメントされている行 1、2、3、および 4 で何を達成していますか?

お時間をいただきありがとうございます。

4

1 に答える 1

3

クイックソート アルゴリズムの強みは、データを半分に分割し、各半分を並べ替えて結果をマージすることです。この動作により、O(N log N) の複雑さが生じます。ただし、これは、そのデータを半分に分割すると、実際には半分に分割されるという事実に基づいています。ただし、これは常に正しいとは限りません。配列を分割するだけでなく、2 つの部分に分割していますが、各要素をパーティション要素 (P など) と比較しています。要素が P 以下の場合は左側のサブ配列に入り、それ以外の場合は右側のサブ配列に入ります。そのため、サブ配列のサイズはパーティション要素に大きく依存します。P が配列内の最大値または最小値に等しい場合、サブ配列の 1 つが空になり、クイックソートは「分割フェーズ」から何も得られません。

「3 の中央値」メソッドは、選択された 3 つの要素の中間の値の要素にすることで、パーティション要素が配列の最大または最小の要素になるのを防ぎます。

コード内の fours 行は、3 つの要素を適切な場所に効果的に並べ替え、中央の要素を新しいパーティションとして選択しています。3 つの要素を比較して中央値を決定する場合は、それらを同時に並べ替えることもできます。

于 2012-11-15T15:10:33.870 に答える