高速節約のためのソートアルゴリズム
スペースを無駄にせず、より高速なソートアルゴリズムはありますか？それが「クイックソート」です！名前を聞いただけで、高級そうだと思いませんか？
ここで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は配列の1の位置にあります。目標は6を数列の真ん中の位置に移動させることで、その位置を仮にkとします。さて、そのkを見つけ、k番目の位置をカットオフ・ポイントとして、左側の数字がすべて6以下、右側の数字がすべて6以上となるようにします。考えてみてください、そんな方法があるでしょうか？
並べ替えアルゴリズム
方法はとても簡単で、「6 1 2 7 9 3 4 5 10 8」という初期配列の両端から「プロービング」を開始します。右から左へ6より小さい数を見つけ、次に左から右へ6より大きい数を見つけ、それらを入れ替えます。ここで、iとjという2つの変数を使うことができ、それぞれ数列の左端と右端を指します。この2つの変数に "Sentry i "と "Sentry j "というキャッチーな名前を付けます。はじめに、sentry iが数列の左端、数字の6を指し、sentry jが数列の右端、数字の6を指すとします。
まずセントリーjが動き出します。ここで設定されている基本数字は一番左の数字なので、セントリーjが最初に動き出すことが非常に重要です（その理由は自分で考えてください）。セントリーjは6より小さい数字を見つけて止まるまで、一歩一歩左へ移動します。次の歩哨iは6より大きい数字を見つけて止まるまで一歩ずつ右へ移動します。***歩哨jは数字の5の前で止まり、歩哨iは数字の7の前で止まります。
ここで、センチネルiとセンチネルjが指す要素の値を交換します。交換後のシーケンスは次のようになります：
6 1 2 5 9 3 4 7 10 8
ここで○○交換終了。次のスタートセントリーJは左に移動し続けます。4を見つけて停止。歩兵iも右に動き続け、9を見つけたところで停止。この時点で再び交換が行われ、交換後のシークエンスは以下の通り：
6 1 2 5 4 3 9 7 10 8
回目の交換が終わり、「探知」が続行。セントリーjは左に移動し続け、3を発見して停止。偵察兵iは右に移動し続け、やばい！セントリーiとセントリーjがこの地点で出会い、セントリーiとセントリーjがともに3に近づきます。これで「探査」は終了。ベース6と3を交換。交換後のシークエンスは以下の通り：
3 1 2 5 4 6 9 7 10 8
この****ラウンドの "検出 "は本当に終わりました。先ほどのプロセスを思い出してみてください。
OK、説明完了。これで塩基配列の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
OK、これで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,n;//グローバル変数を定義する、この2つの変数はサブファンクションで使用する必要がある
void quicksort(int left,int right)
{
int i,j,t,temp;
if(left>right)
return;
temp=a[left]; //tempデータは
i=left;
j=right;
while(i!=j)
{
//順序は重要である。
while(a[j]>=temp && i<j)
j--;
//右からもう一度探す
while(a[i]<=temp && i<j)
i++;
//配列中の2つの数値の位置を入れ替える
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//データムを確定する
a[left]=a[i];
a[i]=temp;
quicksort(left,i-1);//左側に引き続き、再帰的な処理を紹介しよう。
quicksort(i+1,right);//继续处理右边的 ，这里是一个递归的过程
}
int main()
{
int i,j,t;
//データを読む
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
quicksort(1,n); //クイック・ソート・コール
//ソート結果を出力する
for(i=1;i<=n;i++)
printf("%d ",a[i]);
getchar();getchar();
return 0;
}
結果は
姿勢づくりセッション
クイックソートは1960年にC.A.R.Hoareによって発表され、その後多くの人によって最適化されてきました。クイックソートに興味がある方は、Tony Hoareの1962年のComputer Journalの論文 "Quicksort "とIntroduction to Algorithmsの第7章をご覧ください。クイックソートのアルゴリズムは、トニー・ホールのコンピューティングにおける才能の最初の兆候にすぎず、彼は後に上司から、新しいマシンのための新しい高級言語を設計するよう求められました。当時はまだPASCALやC言語などなかったのです。トニー・ホールは、エドガー・ウィベ・ダイクストラが主催した「ALGOL 60」トレーニング・コースに参加し、新しい言語を設計する代わりに、既存の「ALGOL 60」を改良して社内で使えるようにすべきだと考えました。新しい言語を設計する代わりに、会社の新しいマシンで使えるように、既存の『ALGOL 60』を改良すべきだと考えたのです。そこで彼は、ALGOL 60のサブセット・バージョンを設計しました。このバージョンは、当時ALGOL 60の中で最も効率的で信頼性の高いものでした***。その後、「ALGOL X」の設計では、よく知られた「case」文も考案し、これは後にPASCAL、C、Javaなど、さまざまな高級言語で広く採用されるようになりました。もちろん、トニー・ホールのコンピュータ分野への貢献はもっともっと多く、彼は1980年にチューリング賞を受賞しています。
アルゴリズムのチュートリアルについては、こちらをご覧ください：
