トイレに座ってアルゴリズムを見る: クイックソート

高速かつ経済的なソートアルゴリズム

スペースを無駄にせず、より高速なソートアルゴリズムはありますか?それが「クイックソート」です！名前を聞くだけで、とても高級感が感じられますよね？

ここで、10 個の数字「6 1 2 7 9 3 4 5 10 8」を並べ替えるとします。まず、このシーケンス内の数字を基本数として選択します (この用語に怖がらないでください。これは参照用に使用される数字にすぎず、後で何に使用されるかがわかります)。便宜上、最初の数字 6 を基数とします。次に、この数列の中で基数より大きい数字をすべて 6 の右側に配置し、基数より小さい数字を 6 の左側に配置する必要があります。配置は次のようになります。

3 1 2 5 4 6 9 7 10 8

初期状態では、数字 6 がシーケンスの最初の位置にあります。私たちの目標は、この位置が k であると仮定して、6 をシーケンスの中央の位置に移動することです。ここで、この k を見つけて、k 番目の桁を分割点とする必要があります。左側の数字は 6 以下で、右側の数字は 6 以上です。考えてみてください。これを実現する方法はあるでしょうか?

ソートアルゴリズムの威力

方法は実際には非常に簡単です。最初のシーケンス「6 1 2 7 9 3 4 5 10 8」の両端から「検出」を開始します。まず、右から左へ6 未満の数字を探し、次に左から右へ6 より大きい数字を探し、それらを交換します。ここでは、2 つの変数 i と j を使用して、それぞれシーケンスの左端と右端を指すことができます。これら 2 つの変数に、「Sentinel i」と「Sentinel j」というわかりやすい名前を付けます。最初は、センチネル i がシーケンスの一番左 (つまり i=1) を指し、数字 6 を指すようにします。センチネル j がシーケンスの右端 (つまり = 10) を指し、その数字を指すようにします。

まず、センチネルJが移動を開始しました。ここで設定される基数は一番左の数字なので、センチネル j を最初に出すことが非常に重要です (なぜか考えてみてください)。センチネル j は、6 未満の数字が見つかるまで、段階的に左に移動します (つまり、j--)。次に、センチネル i は、6 より大きい数字が見つかるまで、右に 1 ステップずつ移動します (つまり、i++)。 ***センチネル j は 5 番の前で停止し、センチネル i は 7 番の前で停止しました。

ここで、sentinel i と sentinel j が指す要素の値を交換します。スワップ後のシーケンスは次のとおりです。

6 1 2 5 9 3 4 7 10 8

この時点で最初のやり取りは終了です。次に、Sentinel J は左に移動し続けます (もう一つの親切なリマインダーとして、Sentinel J は毎回最初に開始する必要があります)。彼は 4 (基数 6 より小さく、要件を満たしていた) を見つけたところで止まりました。センチネル i も右へ進み続けました。彼は 9 (基数 6 よりも大きく、要件を満たしていた) を見つけたところで停止しました。このとき、再度交換が行われ、交換後のシーケンスは次のようになります。

6 1 2 5 4 3 9 7 10 8

2 回目の交換が終了し、「検出」が続行されます。歩哨 j は左へ移動し続け、3 (基数 6 より小さく、要件を満たしている) を見つけた後、再び停止しました。センチネル i は右に移動し続けます、ああ、だめだ!このとき、歩哨 i と歩哨 j が出会い、歩哨 i と歩哨 j は両方とも 3 まで歩きました。これは「検出」が終了したことを意味します。基数 6 と 3 を交換します。スワップ後のシーケンスは次のとおりです。

3 1 2 5 4 6 9 7 10 8

これで今回の「検出」は終了です。このとき、基数6を分割点として使います。6の左側の数は6以下、6の右側の数は6以上です。先ほどのプロセスを振り返ってみましょう。実際、センチネル j のミッションは参照数より小さい数を見つけることであり、センチネル i のミッションは i と j が出会うまで参照数より大きい数を見つけることです。

はい、以上です。これで基数 6 が復元され、数列の 6 番目になりました。この時点で、元のシーケンスは 6 を分割点として 2 つのシーケンスに分割されています。左側のシーケンスは「3 1 2 5 4」、右側のシーケンスは「9 7 10 8」です。次に、これら 2 つのシーケンスを個別に処理する必要があります。 6 の左側と右側のシーケンスがまだ非常にわかりにくいためです。しかし、それは問題ではありません。私たちはすでにその方法を習得しています。次に、前の方法をシミュレートして、6 の左側と右側のシーケンスをそれぞれ処理するだけです。次に、6 の左側のシーケンスを扱います。

左側のシーケンスは「3 1 2 5 4」です。このシーケンスを 3 を基数として調整し、3 の左側の数字が 3 以下になり、3 の右側の数字が 3 以上になるようにしてください。さあ、書き始めましょう。

シミュレーションが正しければ、調整後のシーケンスは次のようになります。

2 1 3 5 4

はい、これで 3 が元の位置に戻りました。次に、3 の左側のシーケンス「2 1」と右側のシーケンス「5 4」を処理する必要があります。数列「2 1」は2を基数として調整されます。処理後、数列は「1 2」となり、2は元の位置に戻ります。シーケンス「1」には数字が 1 つだけ含まれており、処理は必要ありません。これまでに、シーケンス「2 1」の処理が完了し、シーケンス「1 2」が取得されました。シーケンス「5 4」の処理もこのメソッドと同様であり、結果のシーケンスは次のようになります。

1 2 3 4 5 6 9 7 10 8

新しいサブシーケンスが生成されなくなるまで、シーケンス「9 7 10 8」に対して同じプロセスが繰り返されます。最終的に、次のようなシーケンスが得られます。

1 2 3 4 5 6 7 8 9 10

この時点でソートは完了です。注意深い生徒は、クイックソートの各ラウンドは、実際には、すべての数字がリセットされてソートが完了するまで、そのラウンドのベース数をリセットするためのものであることに気付いたかもしれません。以下はアルゴリズム全体の処理を説明する支配的な図です。

これはなぜでしょうか?

クイックソートが高速な理由は、バブルソートと比較して、各交換がジャンプのようなものだからです。並べ替えるたびに、基準点を設定し、基準点以下のすべての数値を基準点の左側に配置し、基準点以上のすべての数値を基準点の右側に配置します。こうすることで、交換するたびに、隣り合う数字同士しか交換できないバブルソートのようにならず、交換距離がずっと大きくなります。そのため、比較や交換の総回数が減り、速度も自然と向上します。もちろん、最悪の場合、隣接する 2 つの数字が入れ替わってしまう可能性もあります。したがって、クイックソートの最悪の時間計算量はバブルソートと同じで、どちらも O(N ² ) であり、平均時間計算量は O(NlogN) です。実際、クイックソートは「バイナリ検索」と呼ばれるアイデアに基づいています。 「バイナリ」思考については後で取り上げますが、そのときはそれについてお話しします。まず、コードは次のようになります

#include <stdio.h>  
 int a[101],n; //グローバル変数を定義します。これらの2つの変数はサブ関数で使用する必要があります 
 voidクイックソート( int左, int右)
 {
整数i、j、t、温度;
 （左＞右）の場合
戻る; 
                                
    temp=a[left]; //tempは基数を格納する 
    i=左;
    j=右;
一方(i!=j)
    {
 //順序は非常に重要です。まず右から始めてください 
 (a[j]>=temp && i<j)であるとき
                            j--;
 //右側のものを探す 
 (a[i]<=temp && i<j)の間
                            私は++;
 //配列内の2つの数値の位置を交換する 
もし(i<j)
                   {
                            t = a[i];
                            a[i] = a[j];
                            a[j] = t;
                   }
    }
 //最後にベンチマーク番号を返します 
    a[左]=a[i];
    a[i] = 一時; 
                             
    quicksort(left,i-1); // 左側の処理を続けます。これは再帰的なプロセスです。  
    quicksort(i+1,right); //右側の処理を続けます。これは再帰的なプロセスです。  
 }
 intメイン()
 {
整数i,j,t;
 //データを読み取る 
    scanf( "%d" ,&n);
 (i=1;i<=n;i++)の場合
                   scanf( "%d" ,&a[i]);
    quicksort(1,n); //クイックソート呼び出し  
                             
 // ソートされた結果を出力する 
 (i=1;i<=n;i++)の場合
        printf( "%d " ,a[i]);
    getchar();getchar();
 0を返します。
 }

1061279345108

実行の結果は

12345678910

姿勢トレーニングセッション

クイックソートは 1960 年に CAR Hoare (Charles Antony Richard Hoare) によって提案され、それ以来多くの人々がさらなる最適化を行ってきました。クイックソートに興味がある方は、Computer Journal に掲載された Tony Hall の 1962 年の論文「Quicksort」と「Introduction to Algorithms」の第 7 章を​​お読みください。クイック ソート アルゴリズムは、コンピューター分野におけるトニー ホールの才能が初めて発揮されたにすぎませんでした。その後、彼は上司に高く評価され、再び起用され、会社は彼が新しいマシン用の新しい高級言語を設計してくれることを期待しました。当時は PASCAL や C 言語のような高度なものは存在しなかったことを知っておく必要があります。その後、トニー・ホールはエドガー・ワイブ・ダイクストラ（1972年のチューリング賞受賞者。この偉人とは後ほどお会いして詳しくお話しします）が主催する「ALGOL 60」トレーニング クラスに参加しました。彼は、自信のないまま新しい言語を設計するよりも、既存の「ALGOL 60」を改良して、会社の新しいマシンで使用できるようにしたほうがよいと考えました。そこで彼は「ALGOL 60」のサブセットバージョンを設計しました。このバージョンは、実行効率と信頼性の点で当時の「ALGOL 60」のすべてのバージョンの中で最も優れていたため、トニー・ホールは国際的な学術コミュニティから注目を集めました。その後、彼は「ALGOL X」の設計において有名な「case」文を発明し、これは後にPASCAL、C、Javaなどのさまざまな高級言語に広く採用されました。もちろん、トニー・ホールはコンピュータ分野にさらに多くの貢献をしており、1980 年にチューリング賞を受賞しました。

その他のアルゴリズムのチュートリアルについては、以下をご覧ください。

http://ahalei.blog..com/