🙍🏽 🚹 🐗 並べ替えについて（バブル、クイック、コーム...） 👏🏽 🔎 🛢️

この記事の主な目的は、初心者プログラマーです。一般的な並べ替えについて、およびインターネットの見出しで言及されている記事の海について、なぜもう1つ必要なのですか？たとえば、ハブに関する良い記事があります：バブルソートとすべてすべて。第一に、あまり良いものはありません。第二に、この記事では「なぜ、何、どのように、なぜ」という質問に答えたいと思います。なぜソートが必要なのですか？まず、データの検索と表示用。未ソートのデータを使用するタスクには、解決が非常に困難なものと、不可能なものがあります。例：単語がアルファベット順にソートされているスペルチェック辞書。そうでない場合は、正しい単語を見つけてください。サブスクライバーがアルファベット順にソートされている電話帳。並べ替えがオプションであり、あまり必要ではない場合でも、並べ替えられたデータを使用すると便利です。

どのような種類のデータをソートしますか？比較と交換を使用して、配列内の整数データをソートします。つまり配列のm [i]とm [j]（i <j）の要素を比較し、j番目がi番目より「小さい」場合、それらを交換します。結果として、配列は昇順でソートされます。
注：比較するので、m [j] / 10 <m [i] / 10です。これは、同じキーを持つアイテムがどのようにソートされるかを確認するために行われます。この比較では、30 <40、ただし30 = 31 = 32 ...安定（または安定した並べ替え）は、同じ比較キーを持つ要素の順序を変更しません（この例では、比較キーは/ 10要素の値の整数部分です）

以下は初期（未ソート）配列です。

ソート済み：

注：要素32、31、30の順序が変更されました。ソートは安定していません（安定していません）。

この記事で使用されているすべての並べ替えは、いくつかの要素を比較し、それらが正しい順序になっていない場合は変更します。それらはどう違うのですか？比較する要素のペアを選択する方法が異なります。
以下は、Cのソート手順の例です。どこでも、最初のパラメーターは配列のアドレス、2番目は配列内の要素の数です。プロシージャの外側のループはパスと呼ばれ、内側のループは単純にループです。

簡単な仕分け

パスは配列のすべての要素を反復処理し、ループ内で現在の要素と後続のすべての要素を比較します。

void sorto(int *m,int n) // , , ...  { int tmp; for (int i=0;i<n-1;++i) { //  for (int j=i+1; j<n;++j) { //  if (m[j]/10<m[i]/10) { // j- ,     i- tmp=m[i]; m[i]=m[j]; m[j]=tmp; } } } }

作業結果

シンプルな並べ替えに加えて、実装が簡単で安定しています。
短所-それは非常に遅いので多くの比較操作があります。 n個の要素はそれぞれ後続のすべての要素と比較されるため、比較の数は〜n * n / 2です。 n = 100000の場合、比較は50億です。確かに、n = 1000の場合、「唯一」の比較は50万であり、最新のコンピューターは1秒未満でこれを行うことができるため、少量でこのソートが適しています.1つの重要なマイナスがある場合-データがほとんどソートされている場合（10万の要素のうち、10のみがアウトオブプレース）、すべて同じように、動作時間はほとんど変わりません、なぜなら比較操作が多くなります。アルゴリズムを改善して、

バブルソート

「バブル」であり、「バブル」でもあります。内側のループは配列を何度も繰り返し、現在の要素を前の要素と比較します（したがって、実行は1から始まります）。現在の要素が小さい場合は、前の要素と再配置します。順列の場所は変数kに格納され、kのパッセージの終わりにインデックスがあり、そこから配列がソートされます。

 void sortb(int *m,int n) { int tmp,k; while(n>1) { //  ,     k=0; //   for (int i=1; i<n;++i) { if(m[i]/10<m[i-1]/10) { tmp=m[i-1]; m[i-1]=m[i]; m[i]=tmp; k=i; //       } } n=k; //  k   } }

最悪の場合（元の配列が逆の順序で並べ替えられた場合、同じn * n / 2の比較が得られます。最高の場合と良い場合のどちらですか？最良の場合は、配列が完全に短縮された場合です。その後、最初のパスで何も再配置されませんパッセージの終わりにnに0（k = 0）が割り当てられ、2回目のパスはありません。100,000パスの代わりに1つだけです！素晴らしいですが、配列が並べ替えられてもまったく並べられない場合はどうでしょう。たとえば、並べ替えられた配列の最小要素と最大要素を並べ替えて、問題のある「アレイ（30- 32は同じキーを持っています）：

1パスの最初のステップでは、「20」が「50」と比較され、交換が行われます。次のステップでは、「32」が「50」と再び比較されます（現在は「20」の位置を占めています。その結果、最初のパスの終わりに「50」が終わりに置き換わり、残りはすべて1ポジションを配列の先頭に移動します。最初の位置が上にあり、下の位置が下にあると想像すると、通過の結果として最も重いものが下になり、最も軽いものになります。ある記事では、重い要素は「野ウサギ」と呼ばれ、軽い要素は「カメ」と呼ばれます。オード「ウサギ」は、より重要なウサギ（バトンに乗って走る）に出会うか、その場所に着くまで、最後まで（またはdrれ）走ります。、あなたはあなたの場所に到達するためにnパスを必要とします。最も重い（「ペレット」）は1回のパスで素早くownれ、最も軽い（「バブル」）はゆっくりとポップアップします。通路。最軽量が配列の最後にある場合、配列内の要素と同じ数のパスが必要です。

彼らがそれほど干渉しないように、「カメ」をどうするか。救助に来ます

シェーカーソート

泡の選別で重い要素がすぐに沈み、軽い要素がゆっくりと浮くのはなぜですか？比較サイクルは配列の先頭から末尾に移動し、重い要素を「ドラッグ」するためです。そして、最後から最初に移動すると、肺がすぐに現れ、重い肺がゆっくりと沈みます。 1回のパスで最も軽いものが最後から最初に移動します。偶数パスでのシェーカーのソートは、最初から最後まで移動し、奇数セットでは、問題の配列は3パスでソートされます。ほぼソートされたアレイの場合、シェーカーのソートは「バブル」よりもはるかに高速ですが、ランダムにソートされたソースアレイの場合、ゲインは通常それほど大きくありません。

ヘアブラシを並べ替える

または櫛。繰り返しますが、なぜバブルがゆっくりポップアップするのでしょうか？ 通過中に彼は1ポジションに移動するためです。そして、なぜ彼は1ポジションしか動かないのですか？隣接する要素が比較および再配置されるためです。それでは、隣接する要素ではなく、距離s（各パスで徐々にsを減らす）にある要素を比較してみましょう。このアイデアを実践に移すと、櫛でソートすることになります。

 void sortc(int *m,int n) { int tmp,k; int s=n; //    long long cnt=0; while(n>1) { s/=1.247f; //    .      80%   , //         20% if (s<1) s=1; // 0   ,  1 k=0; //   for (int i=0; i+s<n;++i) { // ,    ( s  )   if(m[i]/10>m[i+s]/10) { tmp=m[i]; m[i]=m[i+s]; m[i+s]=tmp; k=i; } ++cnt; } if (s==1) //  1,    .   n=k+1; } }

アイデアは単純なようで、アルゴリズムは複雑ではありませんが、結果は印象的です。櫛の並べ替えは、バブル/シェーカーよりもはるかに高速であることが判明し、「迅速な」qsort並べ替えを追い越すことさえできます。しかしマイナスがあります-それは安定していません（直感的に明らかです）。

Qsortクイックソート

配列のクイックソート機能は非常に簡単です。

 //   qsort int fcomp(const void *i, const void *j) { return (*(int *)i)/10 - (*(int *)j)/10; } void sortq(int *m,int n) { qsort(m,n,sizeof(int),&fcomp); }

標準のqsortクイックソートを使用するため、単純です。与えられたアルゴリズムをもう一度見てみましょう。全体で、要素のペアm [i]とm [j]が選択され、比較されます。しかし、m [i]とは何ですか？これは、整数mの配列のi番目の要素、または「アドレスAi = m + i * <sizeof（int）>にある要素」です。したがって、j番目の要素はアドレスAj = m + j * <sizeof（int）>にあります。そのため、アドレスAiとAjの要素を比較し、Aj <Aiの場合はそれらを再配置します（適用する比較演算の意味ではこれよりも少ない）。したがって、qsort関数は、配列（最初のパラメーターとして渡される）から要素を選択、比較、および再配置する一種の並べ替えプロセッサです。当然、配列内の要素の数を知る必要があり、2番目のパラメーターによって渡されます。 qsortはi番目の要素の位置をどのように決定しますか？非常に簡単-i * <バイト単位の要素サイズ>を配列アドレスに追加します。この<size in bytes>は、3番目のパラメーターによって渡されます。わかりましたが、qsortはどのように要素を比較しますか？彼女は自分自身を比較するのではなく、アドレスが4つのパラメーターで渡される比較関数fcompを使用します。 qsortが内部アルゴリズムでiおよびj番目の要素を比較する必要があると判断すると、アドレスを1および2パラメーターとしてfcomp関数に渡し、fcomp関数は比較結果を返します<0、= 0、> 0 2番目のパラメーターは等しいかそれ以上です。 qsortがi <jであるがfcomp（＆m [i]、＆m [j]）> 0である場合、彼女は単純に配列内の要素を交換します（要素のサイズは知っていますが、内容は重要ではありません）。

ソート時間10,0001アイテム

Intel i5プロセッサ（3.3 GHz）を搭載したコンピューターで100001要素を含む配列の並べ替え時間を測定してみましょう。時間は秒単位で示され、分数はパスの数を示します（クイック並べ替えの場合は不明です）。順序付けられた、最初と最後の要素のみが再配置された）絶対的なリーダー。理想的には、このデータの「グラウンド」です。しかし、ランダムデータでは、combとqsortによる並べ替えはライバルにチャンスを与えません。問題のある配列でのバブルソートでは、単純に順列操作の数が桁違いに少ないため、ランダムに比べて速度が2倍になります。

仕分け	シンプル	バブル	シェーカー	ヘアブラシ	高速（qsort）
安定した	+	+	+	-	-
ランダム	23.1 / 100000	29.1 / 99585	19.8 / 50074	0.020 / 49	0.055
問題のある	11.5 / 100000	12.9 / 100000	0.002 / 3	0.015 / 48	0.035
逆	18.3 / 100000	21.1 / 100000	21.1 / 100001	0.026 / 48	0.037

そして、原点に戻って、バブルソートと、ソートプロセスを直接見てみましょう。最初のパスで重い要素（50）が最後まで運ばれる方法をご覧ください。

比較されたアイテムは緑のフレームで表示され、再配置されたアイテムは赤のフレームで表示されます

公開後の追加

私はqsortが悪いとか遅いとは思わない-それは十分に速く、機能的であり、可能であれば使用すべきである。はい、彼女は比較関数を呼び出すのに時間を費やさなければならず、「インプレース」を比較する「櫛」に道を譲りました。 この遅れは重要ではありません（qsortからのバブルの遅れと比較してください。これは配列の成長とともに増加します）。ここで、数値ではなく、特定のフィールドのある種の複雑な構造を比較し、この構造を1000バイトで構成する必要があります。配列に10万個の要素を配置し（100mbは何か）、qsortを呼び出します。 fcomp関数（比較関数）は必要なフィールドを比較し、結果はソートされた配列です。同時に、qsort要素を再配置する場合、1000バイトのフラグメントを3回コピーする必要があります。そして今、「小さなトリック」-ソース要素への10万リンクの配列を作成し、このリンク配列の先頭をqsortに渡します。 qsortリンクを交換する場合、リンクは1000ではなく4バイト（64ビット8）であるため、これらの4/8バイトを変更する必要があります。もちろん、パラメータとして要素のアドレスではなく要素のアドレスのアドレスを受け取るため、fcompを変更する必要があります（ただし、これは単純な変更です）。しかし、今では、いくつかのソート関数を作成できます（それぞれが構造体フィールドでソートします）。また、必要に応じて、複数のリンクの配列を作成できます。 qsortが提供する多くの可能性があります！

ところで、オブジェクト自体の代わりにオブジェクト参照を使用すると、qsortが呼び出されるときだけでなく、ベクター、セット、マップなどのコンテナーを使用するときにも役立ちます。

比較と交換の数

次の表は、比較操作の数/各ソートの交換の数を示しています。 qsortの場合、交換の数は不明であるため、比較の数のみが表示されます。ランダム配列の場合、qsortの比較の数は最小限であることがわかります。

仕分け	シンプル	バブル	シェーカー	ヘアブラシ	高速（qsort）
ランダム	5'000'050'000 / 1'131'715'503	4'999'702'086 / 2'507'142'238	3'341'739'679 / 2'507'142'238	4'489'129 / 714'533	1'915'414
問題のある	5'000'050'000 / 199'999	5'000'050'000 / 199'999	299'997 / 199'999	4'395'305 / 91'829	1'588'741
逆	5'000'050'000 / 5'000'050'000	5'000'050'000 / 5'000'050'000	5'000'050'000 / 5'000'050'000	4'395'305 / 233'210	1'588'741

並べ替えについて（バブル、クイック、コーム...）