クイックソートアルゴリズムの詳細な分析

[[121946]]

序文

以前、このブログでクイックソートアルゴリズムに関する人気のチュートリアル記事を書きましたが、多くのネットユーザーからこの記事はわかりやすいと言われました。しかし、その後、algorithm__というネットユーザーが「クイックソートアルゴリズムは、どのようにして列を段階的に導き出したのか？PとNPの問題のようなものだ。解法がわかれば証明は難しくない。しかし、解法がわかる前に、少しずつ段階的に推論しなければならない。それはどれほど難しいことか？」と指摘した。

実際、私はこの質問について何度も考えてきました。私は以前、このことについてブログで何度も言及しました。では、なぜ多くの人が私が書いたクイック ソート アルゴリズムを読んで、しばらくするとクイック ソートが何なのかわからなくなるのでしょうか。

「その大きな理由は、表面しか知らず、中身を知らず、用途しか知らず、本質を知らないからです。本質を見れば多くのことがわかります。しかし、ほとんどの人はこれをやりません。その結果、読んでは忘れ、忘れてまた読むのです。このように、知識を繰り返し暗記する中で、本質を分析することができず、悪循環に陥っています。」

したがって、結局のところ、何かを学ぶには、それを自由に使用できるだけでなく、その原理、起源、本質を理解する必要があります。侯潔氏が言ったように、使い方は知っていても原理を知らないのは、あまり賢いとは言えません。あなたが提起した質問はとても良いです。クイックソートアルゴリズムがどのように設計され、どのようにして実現されたかを段階的に詳しく説明する別の記事を書く予定です。 ”

さて、これからこのクイック ソート アルゴリズムを徹底的に分析し、読者がこのアルゴリズムを本当に理解し、その詳細を知り、その内部原理を理解できるようになることを願っています。この論文では、クイックソートアルゴリズムのプロセスの起源と時間の複雑さを分析することに焦点を当てています。

1. クイックソートの初期バージョン

クイックソート（当時はクイックソートと呼ばれていませんでした）というアルゴリズムのアイデアは、もともとCAR Hoareという人物によって提案されました。彼が提案したアルゴリズムのアイデアの具体的なバージョンは次のとおりです。

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]を交換する
それ以外 戻る​

その後、このバージョンには多くの類似のバリエーションが生まれました。以下、詳細に分析していきます。

2. ホーア版の具体的な分析

Hoare は、『アルゴリズム入門』の第 7 章の質問 7-1 でこれについて詳しく説明しています。

上で見たように、Hoare のクイック ソート バージョンは、それぞれ先頭と末尾を指す 2 つのポインタを比較することによってソートできます。

以下では、このバージョンを分析します。

I. 2 つのポインター、i はシーケンスの先頭を指し、j は末尾を指します。つまり、i=1、j=n です。配列の最初の要素 ki を主要素として取得します。つまり、key<-ki (割り当て) です。

II. 代入演算（注：「->」は代入を意味します）

j (小さい方を探す)、右から左へ、連続的に --、キーより小さい最初の要素 kj に遭遇するまで、ki<-kj。

i (大きい方を探す)、左から右へ、キーより大きい最初の要素 ki に遭遇するまで ++ を続けます (kj<-ki)。

III. i と j が出会うまで上記の方法を続行し、ki=key となり、ソートの最初のラウンドが完了してから、ステップ II を再帰的に繰り返します。

HOARE-PARTITIONプロセスが完了すると、A[p..j]（中国語版『アルゴリズム入門』第2版には印刷ミスがあり、A[p..r]と印刷されています）内のすべての要素は、A[j+1..r]内のすべての要素以下になります。 HOARE-PARTITION は、以下で紹介する標準の PARTITION パーティション分割方法とは異なります。HOARE-PARTITION では、ピボット値が常に 2 つのパーティション A[p..j] と A[j+1..r] のいずれかに配置されます。 p<<j<<r なので、この除算は必ず終了します。

次に、配列 A=[13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21] に対する上記の HOARE-PARTITION パーティション分割法の演算プロセスを次のように見てみましょう。

i (大きいものを探す) (小さいものを探す) j

13 19 9 5 12 8 7 4 11 2 6 21

私j

13 19 9 5 12 8 7 4 11 2 6 21

私j

6 19 9 5 12 8 7 4 11 2 13 21

じぃ

6 2 9 5 12 8 7 4 11 19 13 21

私j

6 2 9 5 12 8 7 4 11 19 13 21

私j

4 2 9 5 12 8 7 6 11 19 13 21

私j

4 2 5 9 12 8 7 6 11 19 13 21

.....

2 4 5 6 7 8 9 11 12 13 19 21

3. ホーア変種

I. 2 つのポインタ i と j を取ります。最初は i=2、j=n であり、ソートが最終的に完了したときに、左側の部分列の数が右側の部分列の数以下であることを確認します。

II. 正しい姿勢を保ち、変化を続ける

i-->(i は左から右へ移動し、最後の要素よりも大きい要素を探します)

kiとk1を比較すると、分割後にRiが最終的に左部分列の一部になる場合、

次に i++ を実行し、右側に属する部分列 Ri (より大きい) に遭遇するまで i++ を続けます。

<--j (j は右から左へ移動し、最後の要素よりも小さい要素を探します)

同様に、j--、左の部分列に属するより小さい要素Rj（より小さい）に遭遇するまで、

このように、i<j のときは、Ri と Rj を交換します。つまり、ma の位置を並べ替えて、小さい方を左側に、大きい方を右側に置きます。

III. 次に、i と j が一致するまで、分割されたレコードを同じ方法で処理します。このように、Ri と Rj を常に交換して位置を調整することで、最終的にシーケンス全体がソートされます。

たとえば、次のようになります（2 は主要素です）。

i-> <-j (小さい方を探す)

2 8 7 1 3 5 6 4

jが指す要素4は2より大きいので、j--、

私 <--j

2 8 7 1 3 5 6 4

このプロセス中に、j が 2 より小さい要素に遭遇しない場合、j は 1 を指すまで増加し続けます。

私j

2 8 7 1 3 5 6 4

この時点で、8と1が入れ替わります。

私j

2 1 7 8 3 5 6 4

この時点で、i が指す要素は 1 であり、これは 2 より小さいため、i は移動せず、j は続行します。j は 2 より小さい要素に遭遇することはなく、最終的に 7 で停止します。

私j

2 1 7 8 3 5 6 4

***、i が指す要素 1 は、シーケンスの最初の要素 k1、つまり 2 と交換されます。

私

[1] 2 [7 8 3 5 6 4]

このように、2 はシーケンス全体を 2 つの部分に分割します。次に、ソートする残りの数字が 2 回目と 3 回目のラウンドで再帰的にソートされます。

上記のプロセスから、このアルゴリズムの不器用さが大まかにわかります。たとえば、上記のステップ *** で、j が 2 より小さい要素を見つけられない場合、j-- と前進し続ける必要があります。 2 番目に、i が指す要素が交換された後、i が指す要素がこの時点で 2 未満であることを保証する方法はありません。つまり、i ポインタは元の場所に留まり続け、移動することはできません。そのような滞在には確かにかなりの時間がかかるでしょう。

その後、セジウィックはソート速度が速いことからこれを「クイックソート」と名付け、クイックソートが誕生しました。やがて有名になり、20 世紀の 10 大アルゴリズムの 1 つになりました。

さて、次に、Hoare のバリアントアルゴリズムを見てみましょう。次のように、3 8 7 1 2 5 6 4 のシーケンスを並べ替えます。

1. j-- は、シーケンス内でキー値 3 より小さい最初の要素 2 に遭遇するまで、ki に 2 を割り当て、j は空の要素を指すようになります。

私j

3 8 7 1 2 5 6 4

私j

=> 2 8 7 1 5 6 4

2. 8 を指す i++ は、8 を j が指す要素の空白スペースにリセットし、i が指す要素は再び空になります。

私j

2 8 7 1 5 6 4

私j

=> 2 7 1 8 5 6 4

3. j は -- を続け、1 に遭遇しますが、これはまだ 3 (事前に保存されたキー値) より小さいので、i が指す空白スペースに 1 を割り当てます。

私j

2 7 1 8 5 6 4

=> 2 1 7 8 5 6 4

4. 同様に、i は ++ を続け、key より大きい 7 に遭遇します。7 は j が指す空白スペースに割り当てられます。その後、i と j が出会います。 ***旅の終わり:

私j

2 1 7 8 5 6 4

私j

=> 2 1 7 8 5 6 4

5. ***、以前に保存したキー 3 を ki、つまり i が指す空白スペースに割り当てると、次のようになります。

[2 1] 3 [7 8 5 6 4]

つまり、全体は次のようになります。

3 8 7 1 2 5 6 4

2 8 7 1 3 5 6 4

2 3 7 1 8 5 6 4

2 1 7 3 8 5 6 4

2 1 3 7 8 5 6 4

2 1 3 7 8 5 6 4

後続の補足:

ソートするシーケンスが逆シーケンスの場合はどうなるでしょうか? わかりやすくするために、シーケンス 9 8 7 6 5 4 3 2 1 をソートする別の例を見てみましょう。

9 8 7 6 5 4 3 2 1 //9は主要素です

1 8 7 6 5 4 3 2 //j は右から左に最小の数字を検索し、1 を見つけてそれを *** 番目の数字に割り当てます。

1 8 7 6 5 4 3 2 //i は左から右に最大の数字を探しますが、j に出会うまで見つかりません

1 8 7 6 5 4 3 2 9 //***、9 を記入してください。

前述のように、配列がすでに逆順にソートされている場合、配列のソートには O(N^2) の時間計算量が必要であることが簡単にわかります。クイックソートの時間計算量については、本文の後半で詳しく分析します。

***、このアルゴリズムを実装するプログラムを次のように記述します。あまり説明する必要はないと思います。

 int partion( int data[], int lo, int hi) // 何でもかんでも引用。   
 
 { 
 
 intキー = データ[lo]; 
 
 int l = lo; 
 
 h = hi ; 
 
一方(l<h) 
 
   { 
 
 while (key<=data[h] && l<h) h--; // 上位にある小さい方を検索し、見つかった場合は先頭に移動します  
 
          データ[l]=データ[h]; 
 
 while (data[l]<=key && l<h) l++; // 下の位置にある大きい方を検索し、見つかった場合は後ろに移動  
 
         データ[h]=データ[l]; 
 
   } // このように、小さい方が前にあり、大きい方が後ろにあり、2つに分かれています  
 
    データ[l]=キー; 
 
 lを返します。 
 
 }

後続の補足：例えば次のようになります（ソートの最初のラウンドのみを説明します）。

3 8 7 1 2 5 6 4

2 8 7 1 5 6 4

2 7 1 8 5 6 4

2 1 7 8 5 6 4

2 1 7 8 5 6 4

2 1 3 7 8 5 6 4 //***記入、キーワード3

これを見て、読者の皆さんは前回の記事のクイックソートの 2 番目のバージョンを思い浮かべたでしょうか? はい、上記のプログラムはその記事の 2 番目のバージョンです。プログラムを取り出してみます。一度見れば理解できると思います。

 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); //標準値の右半分に対してこの関数を再帰的に呼び出します 
  }
 }

この時点で、十分に明確に説明できたと思います。まだ理解できないなら、指を伸ばして数えてみてください...。では、読者にもう一つ質問しましょう。この場合、i は左から右に検索され、key より大きい最初のものが見つかると (配列の最初の要素が key として設定されます)、kj はリセットされます。j は右から左に検索され、key より小さい最初の要素が見つかると、ki はリセットされます。もちろん、このプロセスでは、i と j は常に変化し、++ または -- を通じて異なる要素を指します。

クイックソートアルゴリズムの考え方に似た状況を実生活で思い浮かべたことはありますか？思いついたら、今からでも遅くはありませんので教えてください。 :D.

4. クイックソートの最適化バージョン

その後、N. Lomuto は新しいバージョンを提案しました。これは、クイック ソート アルゴリズムで説明された最初のバージョン、つまり最適化された PARTITION 手順であり、現在は「アルゴリズム入門」という本に記載されています。

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

パーティション(A, p, r)

 x ← A[r] // 最後の要素A[r]を主要素として取る 
私 ← p - 1
 j ← p to r - 1 //注意: j は r ではなく、p から r-1 を指します。   
 
する  A[j] ≤ xの場合
           i ← i + 1 となる
                A[i] <-> A[j] を交換する
A[i + 1] <-> A[r]を交換する
i + 1を返す

次に、配列全体を再帰的にソートします。

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

最初の例、2 8 7 1 3 5 6 4 を見てみましょう。違いは、最初の要素を主要素とするのではなく、最後の要素 4 を主要素としていること、および i ポインターと j ポインターの両方が最初から始まり、j が前、i が後ろにあることです。 i は要素の前の位置を参照し、j はソートされるシーケンスの最初の要素を参照します。

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を指します。

私j

2 8 7 1 3 5 6 4

したがって、8 と 1 が入れ替わり、配列は次のようになります。

私j

2 1 7 8 3 5 6 4

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

私は今7を指しています、

私j

2 1 7 8 3 5 6 4

したがって、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

はい、クイックソートの最初のパスが完了しました。以下の工程は省略します。しかし、質問があります。このバージョンと上記のバージョンの間の最適化を見つけることができますか?

5. クイックソートの詳細な分析

上記の最適化バージョンを詳しく分析してみましょう。

パーティション(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を返す

次の配列をソートしてみましょう。各ステップでの変更プロセスは次のようになります。

ip/j

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

私j

2 1 7 8 3 5 6 4

私j

2 1 3 8 7 5 6 4

私

2 1 3 4 7 5 6 8

上記のプロセスから、j が配列全体を 1 回スキャンし、4 より小さい要素に遭遇すると i が ++ し、次に kj と ki が交換されることがわかります。では、j が 4 より小さい要素を見つけたときに、なぜリストを ++ する必要があるのでしょうか。考えてみてください。i が常に同じ場所に留まる場合、毎回 kj と交換される ki は同じ要素ではないでしょうか。この場合、ソートする意味は何でしょうか。

したがって、j が先頭に立ち、i は j の後ろを追従します。j が 4 より小さい要素に遭遇するたびに、i は 1 歩前進し、j が見つけた 4 より小さい要素を i に割り当てます。その後、j は再び前進します。

類推すると、次のように考えることができます。i が実行するすべてのステップは、4 より小さい要素でなければなりません。そうでない場合、i は前進できません。それは、j が先駆者となって i への道を切り開き、i の前に小さな要素を踏み台として置き、i が前進するための道を切り開くようなものです。

この時点で、j は *** までスキャンし、4 より小さいすべての要素を完全に除外しています。*** ピボット要素 4 のみが存在し、これは処理のために i に渡されます。これは、*** ステップで A[i + 1] <-> A[r] が交換されるためです。この方法では、4 より小さいすべての要素が配列の先頭にスワップされることが完全に保証されるだけでなく、j より前に処理されていない大きな要素が後ろにスワップされ、時間の計算量は O(N) になります。このアルゴリズム設計の独創性には感心せざるを得ません。

そこで質問なのですが、上記のPARTITION(A, p, r)バージョンをこれに変更することは可能でしょうか？

読者の皆さんには次のことを考えていただきたいと思います。

 PARTITION(A, p, r) //バージョンについて考えてください。  
  x ← A[r]
  私 ← p - 1
 for j ← p to r //j が p の最後の要素 r を指すようにします 
する  A[j] ≤ xの場合
             i ← i + 1 となる
                  A[i] <-> A[j] を交換する
  A[i + 1] <-> A[r] を交換// この *** ステップを削除 
 return i // i を返します。i+1 は返さなくなりました。  

6. Hoare バリアントと最適化バージョンの比較

さて、問題について考えてみましょう。クイックソートでは、シーケンスの分割について、すでに 2 つのバージョンが上に存在していることがわかります。では、この 2 つのバージョンのどちらが優れているでしょうか。さて、急がずに比較してみましょう。

便宜上、それぞれのアルゴリズムを貼り付けておきます。

ホーア変種:

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]を交換する
それ以外 戻る​

アルゴリズムの紹介からの最適化バージョン:

パーティション(A, p, r)
  x ← A[r] // 最後の要素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を返す

まず、上記の Hoare バージョンの例を取り、シーケンス 3 8 7 1 2 5 6 4 を並べ替えてみましょう。

ホーア変種（主要素が 3 で、主要素が赤）:

3 8 7 1 2 5 6 4

2 8 7 1 5 6 4 // 1回交換して4回比較する

2 7 1 8 5 6 4 // 1回交換、1回比較

2 1 7 8 5 6 4 // 1回交換、1回比較

2 1 7 8 5 6 4 // 1 回交換、0 回比較

2 1 3 7 8 5 6 4 //合計 4 回の交換と 6 回の比較。

// 要素 3、8、7、1、2 が移動されます。移動範囲は 2+3+1+2+4=12 です。

最適化バージョン（ピボットとして 4 を使用）:

3 8 7 1 2 5 6 4 //3と3を入れ替えます。要素を移動する必要がなく、一度比較するだけです。

3 1 7 8 2 5 6 4 // 1回交換して3回比較する

3 1 2 8 7 5 6 4 // 1回交換、1回比較

3 1 2 4 7 5 6 8 // 一度交換して、二度比較します。

//完了しました。合計 4 回の交換と 7 回の比較。

// 要素 8、7、1、2、4 が移動されます。移動範囲は 6+2+2+2+4=16 です。

別の例: 2 8 7 1 3 5 6 4 のシーケンスを並べ替えます。

ホーア変種:

2 8 7 1 3 5 6 4

1 8 7 3 5 6 4 // 1回交換して5回比較する

1 7 8 3 5 6 4 // 1回交換、1回比較

1 2 7 8 3 5 6 4 // 0 回スワップし、1 回比較します。 2 を記入して完了します。合計 2 つの交換と 7 つの比較です。

最適化バージョン:

2 8 7 1 3 5 6 4 //2と2を交換して1回比較する

2 1 7 8 3 5 6 4 // 1回交換して3回比較する

2 1 3 8 7 5 6 4 // 1回交換、1回比較

2 1 3 4 7 5 6 8 // 一度交換して、二度比較します。合計4回の交換と7回の比較が完了しました。

皆さん、この 2 つの例が何も証明していないことはすでにお分かりでしょう。どちらのバージョンがより効率的であるかについては、さらなる検証や数学的証明が必要です。わかりました。もっと有利な証拠が見つかったら、この点について再度議論します。

7. クイックソートアルゴリズムの時間計算量

さて、このクイック ソートを完全に理解できたと思いますので、クイック ソート アルゴリズムの平均時間計算量は O(nlgn) であることがすぐにわかると思います。なぜ列なのでしょうか? ご存知のとおり、配列を 1 回スキャンするのに j,i はどれくらいの時間がかかりますか? はい、もちろん、1 回のスキャンは O(n) なので、列を何回スキャンするかは、lgn 回から n 回までで、最も速いのは lgn 回で、最も遅いのは n 回です。クイックソートの平均時間計算量は O(n*lgn) であることが証明できます。

PARTITION によって可能な最もバランスのとれた分割では、取得される各サブ問題は n/2 より大きくなることはできません。

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

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

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

再帰ツリーの簡単な証明は次のとおりです。

分割統治アルゴリズムの 3 つのステップでは、分解と統合のプロセスにかかる時間がそれぞれ D(n) と C(n) であると仮定します。T(n) をサイズ n のシーケンスの処理にかかる時間とし、サブシーケンスの数を n とし、各サブシーケンスは元のシーケンスの 1/b であり、α は各問題を α 個のサブ問題に分解するのにかかる時間とします。この場合、かかる時間は次のようになります。

n<=cの場合O(1)

T(n) =

αT(n/b) + D(n) + C(n)

クイックソートでは、α は 2、b も 2 で、分解 (つまり、1 と見なすことができる参照ポイントを取得)、マージ (配列を n にマージ) が行われるため、D(n) + C(n) は線形時間 O(n) になります。したがって、時間は次のようになります。

T(n) = 2T(n/2) + O(n) です。

上の図に示すように、各レイヤーの時間計算量は O(n) です。レイヤーは合計で Lgn 個あり、各レイヤーは cn 個なので、消費される合計時間は cn*lgn となり、合計時間は次のようになります。

cn*lg2n+cn = cn(1+lgn) となり、これは O(nlgn) となります。

T(n)<=2T(n/2)+O(n)=>T(n)=O(nlgn)の厳密な数学的証明については、『アルゴリズム入門』の第4章「再帰」を参照してください。

そこで、読者の皆さんに質問したいと思います。クイックソートアルゴリズムの時間計算量についてどう思いますか？マージソートの時間計算量についてどう思いますか？バイナリサーチについてどう思いますか？n 個のノードを持つ赤黒木の高さ lgn についてどう思いますか？…

8. クイックソートから得られるもの

上記のことはずっと昔から考えられてきたことです。この瞬間、私は数日前に見たオランダ国旗の問題を思い出しました。当時、私は algorithm__ と gnuhpc についてこの問題について簡単に議論しました。さて、この問題を詳しく解決してみましょう。

問題の説明:

ランダムに選ばれた赤、白、青のボールを、同じ色の赤、白、青のボールのグループに整列させます。この問題が「オランダの国旗」と呼ばれる理由は、赤、白、青のボールを帯状に並べるとオランダの国旗が形成されると考えることができるからです。次の図に示すように:

[[121948]]

この問題は、クイックソートのパーティション処理に似ています。ただし、開始ポインター 1 つ、現在ポインター 1 つ、終了ポインター 1 つの計 3 つのポインターを使用し、それらを 2 つずつ交換する必要があります。

1. Current は配列シーケンス全体を横断し、current は 1 を指して移動しません。

2. Currentは0を参照し、beginと交換され、その後current++、begin++、

3. 電流は 2 を参照し、end と交換されます。すると、電流は移動せず、end-- になります。

なぜでしょうか? 3 番目のステップでは、current は 2 を指します。end と交換した後、current は移動しません。そうです、algorithm__ が言ったように、current が begin、current++、begin++ と交換される理由は、心配する必要がないためです。電流と終点が交換された後、電流は移動せず、終点は懸念事項のためです。

なぜでしょうか? 考えてみてください。最終的な目標は、0、1、2 を順番に並べることに他なりません。3 番目のステップで、current と end が交換される前に end が 0 を指していて、current が交換された後に current が 0 を指すようになったと想像してください。このとき、current は移動できますか?移動できず、0 を参照し、列を begin と交換する必要があります。

さて、ここまで説明しても、よく理解できないかもしれません。gnuhpc の図を引用するだけで、一目でわかります。

このプログラムの主なコードは次のとおりです。

 //gnuhpc から引用 
 while (現在 <= 終了)
 {
 if (配列[現在] == ​​0)
   {
      swap(配列[現在],配列[開始]);
      現在の++;
      開始++;
   }
それ以外  if (配列[現在] == ​​1)
   {
      現在の++;
   }
それ以外  //配列[current] = 2の場合 
   {
      swap(配列[現在],配列[終了]);
      終わり - ;
   }
 }

この問題はこの記事とはあまり関係がないように思えますが、第一に、この記事の残りの部分でパーティションをすばやくソートするプロセスは似ており、第二に、この問題が少し考えるきっかけとなり、最終的にこの記事の実現につながりました。この記事の冒頭で提起された質問に答えていないことを忘れるところでした。では、クイック ソート アルゴリズムはどのようにして生まれ、段階的にどのように発明されたのでしょうか。答えは簡単です。より多く観察し、より多く考えることです。

さて、もっと観察して考える習慣があるかどうかテストしてみましょう。バブル ソートについて真剣に考えたことがある人がいるかどうかはわかりません。もしそうなら、バブル ソートのシーケンスを改善する方法について考えたことがありますか? わかりました。残りについてはあまり言いませんので、次の写真を投稿してください。

この記事は終了です。

著者: 7月