クイックソートアルゴリズムの普及チュートリアル

[[121950]]

多くは語りません。次に、この記事の主題であるソートアルゴリズムについて説明しましょう。

ご存知のとおり、クイックソートアルゴリズムはソートアルゴリズムのハイライトです。

したがって、この記事はクイックソートから始まります。

------------------------------------------------------

1. クイックソートアルゴリズムの基本的な特徴

時間計算量: O(n*lgn)

最悪の場合: O(n^2)

空間計算量: O(n*lgn)

不安定。

クイックソートは、n 個の数値の入力配列に対して平均 O(nlgn) 時間、最悪の場合は O(n^2) の時間がかかるソートアルゴリズムです。

通常、並べ替えには最適な選択肢です。比較ソートに基づくと、最速でも O (nlgn) にしか到達できないからです。

2. クイックソートアルゴリズムの説明

アルゴリズム入門、第 7 章

クイックソートは分割統治モードに基づいています。

典型的なサブ配列 A[p...r] をソートするための分割統治プロセスは、次の 3 つのステップで構成されます。

1. 分解:

A[p..r]は2つの（空の場合もある）サブ配列A[p ..q-1]とA[q+1 ..r]に分割され、

A[p ..q-1] <= A[q] <= A[q+1 ..r]

2. 解決策: クイックソートを再帰的に呼び出して、サブ配列 A[p ..q-1] と A[q+1 ..r] をソートします。

3. 合併。

3. クイックソートアルゴリズム

バージョン 1:

クイックソート(A, p, r)

 p < rの場合
   q ← PARTITION(A, p, r) //キー 
        クイックソート(A, p, q - 1)
        クイックソート(A, q + 1, r)

配列の分割

クイックソートアルゴリズムの鍵となるのは、A[p..r] のインプレース並べ替えを実行する PARTITION プロシージャです。

パーティション(A, p, r)
  x ← A[r]
  私 ← p - 1
 j ← p から r - 1 まで
する  A[j] ≤ xの場合
             i ← i + 1 となる
                  A[i] <-> A[j] を交換する
  A[i + 1] <-> A[r]を交換する
i + 1を返す

さて、具体的かつ完全な例を挙げてみましょう。

次の配列を素早くソートするには、

2 8 7 1 3 5 6 4 (ピボット)

1つ、

ip/j

2 8 7 1 3 5 6 4 (ピボット)

j は 2<=4 を指しているので、i++、i も 2 を指し、2 と 2 が入れ替わり、元の配列は変更されません。

j は 1 を指すまで戻ります。

二、

j (1を指す) <= 4なので、i++

i は 8 を指しているので、8 と 1 が入れ替わります。

配列は次のようになります。

私j

2 1 7 8 3 5 6 4

3. jは戻って3を指す、3<=4なのでi++

i は現在 7 を指しているので、7 と 3 が入れ替わります。

配列は次のようになります。

私j

2 1 3 8 7 5 6 4

4. j は後方へ移動し続け、4 より小さい数字がないことを発見したので、最後のステップまで実行します。

これは、上記の PARTITION(A, p, r) コードセクションの 7 行目です。

したがって、iは1単位戻り、8を指します。

私j

2 1 3 8 7 5 6 4

A[i + 1] <-> A[r]、つまり8と4が入れ替わるので、配列は最終的に次の形式になります。

2 1 3 4 7 5 6 8

はい、クイックソートの最初のパスが完了しました。

4 配列全体を 2、1、3、7、5、6、8 の 2 つの部分に分割し、2 つの部分を個別に再帰的にすばやくソートします。

ip/j

2 1 3 (ピボット)

2と2を入れ替えても変化なし、次に1と1を入れ替えても変化なし、***、3と3を入れ替えても変化なし、

最後に、3 は 2 1 3 を 2 1 と 3 の 2 つの部分に分割します。

次に 2 1 を再帰的にソートし、最終結果は 1 2 3 になります。

7 5 6 8 (ピボット)、7、5、6はすべて8より小さいので、最後のラウンドは依然として7 5 6 8です。

しかし、この時点では 8 は 7 5 6 8 を 7 5 6 と 8 に割ります。[7 5 6->5 7 6->5 6 7]

次に 7 5 6 を再帰的にソートし、最終結果は 5 6 7 8 になります。

はい、すべてのプロセスと分析が完了しました。

***、私が描いた絵を見てください:

クイックソートアルゴリズムバージョン2

ただし、このバージョンでは、配列の最後の要素 (上記の最初のバージョンのように) がメイン要素として選択されなくなりました。

代わりに、配列の最初の要素をピボットとして選択します。

 /**************************************************************/  
 /* 関数: クイックソートアルゴリズム */  
 /* 関数パラメータ: 構造体型テーブルのポインタ変数タブ */  
 /* 整数変数 left と right の左境界と右境界の添え字 */  
 /* 関数の戻り値: void */  
 /* ファイル名: quicsort.c 関数名: quicksort() */  
 /**************************************************************/  
 voidクイックソート(テーブル *タブ、 int左、 int右)
 {
整数i,j;
 （左<右）の場合
  {
    i=左;j=右;
    tab->r[0]=tab->r[i]; // 今回は左端の要素の値に基づいて分割する準備をし、まずその値を保存します 
する 
    {
 (tab->r[j].key>tab->r[0].key&&i<j)の間
        j--; //右から左へ、標準値より小さい最初の位置 j を見つける 
 if (i<j) //見つかった、位置はj  
      {
        tab->r[i].key=tab->r[j].key;i++;
      } //j番目の要素を左に配置し、iをリセットします 
 (tab->r[i].key<tab->r[0].key&&i<j)の間
        i++; //左から右へ、標準値より大きい最初の位置 i を見つける 
 if (i<j) //見つかった、位置はi  
      {
        tab->r[j].key=tab->r[i].key;j--;
      } // i番目の要素を右端に配置し、jをリセットします 
    }一方で(i!=j);
    tab->r[i]=tab->r[0]; //標準値を最終位置に置くと、除算は完了です 
    quicksort(tab,left,i-1); //標準値の左半分に対してこの関数を再帰的に呼び出します 
    quicksort(tab,i+1,right); //標準値の右半分に対してこの関数を再帰的に呼び出します 
  }
 }

----------------

さて、上記と同じ配列を使用して、クイックソートアルゴリズムのバージョン 2 を適用し、ソートプロセスを示してみましょう。

今回は、配列の最初の要素 2 がピボットとして使用されます。

2(メイン) 8 7 1 3 5 6 4

詳しく見てみましょう:

2 8 7 1 3 5 6 4

i-><-j

（大きいのを探して）（小さいのを探して）

1.j

jは2より小さい最初の要素1を見つけ、iが指す要素2に1を割り当てます（上書きしてリセットします）。

得る：

1 8 7 3 5 6 4

私j

II.

i は 2 より大きい最初の要素 8 を見つけ、j が指す要素に 8 を割り当てます (上書きしてリセットします) (NULL<-8)

1 7 8 3 5 6 4

私 <-j

3.j

j は左に移動し続け、i に出会う前に 2 より小さい要素が見つからないため、プロセスは終了します。

***、メイン要素2が追加されます。

*** 回目の高速ソート後、配列は次のようになります。

1 2 7 8 3 5 6 4

2回目の旅行、

7 8 3 5 6 4

i-><-j

（大きいのを探して）（小さいのを探して）

1.j

j はピボット 7 より小さい 4 を見つけ、7 の位置に 4 を割り当てます。

得る：

4 8 3 5 6

わたし->

II.

i は 7 より大きい最初の要素 8 を見つけ、8 は j (NULL) が指す要素をカバーします。

4 3 5 6 8

私j

4 6 3 5 8

わたし->

i と j が出会い、終わります。

3回目の旅行:

4 6 3 5 7 8

......

以下、分析原理は一貫しているため省略します。

*** の結果は以下の図に示されています。

1 2 3 4 5 6 7 8

上記の内容を詳しく分析すれば、きっと理解していただけると思います。

***、この分類プロセスについて私が描いた絵がこちらです:

以上。 1月5日に追加されました。

さて、上記の 2 つのアルゴリズムのうち、理解する必要があるのは 1 つだけです。

-----------------------------------------------------------

5. クイックソートの最悪ケースと最速ケース。

最悪のケースは、分割プロセスによって生成された 2 つの領域にそれぞれ n-1 個の要素と 1 つの 0 要素が含まれる場合に発生します。

つまり、アルゴリズムのすべての再帰呼び出しで発生すると仮定すると、除算は非対称になります。分割コストはO(n)となり、

サイズ0の配列を再帰的に呼び出した後、T(0) = O(1)が返されるためです。

推定方法の実行時間は、次のように再帰的に表現できます。

T(n)=T(n-1)+T(0)+O(n)=T(n-1)+O(n)。

T(n)=O(n^2)であることが証明できます。

したがって、アルゴリズム内の再帰の各レベルでの分割が極めて非対称である場合、アルゴリズムの実行時間は O(n^2) になります。

つまり、クイックソートアルゴリズムの最悪のケースは、挿入ソートのケースよりも優れているわけではありません。

さらに、配列が完全にソートされると、クイックソートは O(n^2) 時間で実行されます。

同じ状況では、挿入ソートの実行時間は O(n) です。

//注意: この文を理解するには注意してください。ソートの時間計算量について言う場合、それは 1 つの要素のみを指します。

//要素をソートに挿入する、つまり順序付けられたシーケンスに挿入するには n 時間がかかることを意味します。

最も高速なケース、つまり PARTITION によって可能な最もバランスの取れた分割では、得られる各サブ問題が n/2 より大きくなることはないことを証明しましょう。

サブ問題の 1 つのサイズが |_n/2_| であるためです。他のサブ問題のサイズは |-n/2-|-1 です。

この場合、クイックソートの方がはるかに高速です。のために、

T(n)<=2T(n/2)+O(n)。T(n)=O(nlgn)であることが証明できます。

直感的に言えば、クイックソートは再帰ツリーであり、PARTITION は常に 9:1 のパーティションを生成します。

合計実行時間はO(nlgn)です。サブ問題のサイズは各ノードに表示されます。各レイヤーのコストは右側に表示されます。

各レイヤーには定数 c が含まれます。

=============================================

以下のバージョンをご自身で考えてみてください。上記のどのバージョンに該当しますか？

   HOAREパーティション(A, p, r)
 x ← A[p]
私 ← p - 1
 j ← r + 1
 TRUEの場合
j ← j - 1 を繰り返します
         A[j] ≤ xになるまで
       i ← i + 1 を繰り返す
         A[i] ≥ xになるまで
もしi < j
          次にA[i]↔A[j]を交換する
それ以外 戻る

なぜ一部の人々はアルゴリズムをその時点で明確に理解できるのか、私はよく不思議に思う。

しばらくすると、アルゴリズムにまったく慣れず、シーケンスが理解できなくなりますか?

根本的に、このクイックソートアルゴリズムの原理とコンテキストを私はまだ完全に理解していないと思います...

このシリーズをどう改善していくかについては、アルゴリズムを発明した原作者を見つけて、そこからさらに有用なものを掘り出すしかありません。

=========================================

***、クイックソートアルゴリズムのもう 1 つの簡潔な例を次に示します。

クイックソート機能

voidクイックソート( int l, int u)
 { int i, m;
 (l >= u)の場合、戻り値:
    スワップ(l, randint(l, u));
    ｍ＝ｌ；
 (i = l+1; i <= u; i++)の場合
(x[i] < x[l])の場合
            スワップ(++m, i);
    スワップ(l, m);
    クイックソート(l, m-1);
    クイックソート(m+1, u);
 }