分割統治法のようなソートアルゴリズムについては、1つの要素だけが残るまで繰り返すのではなく、特定のしきい値、たとえば30要素に達したときにシフトする方がよいことをMerge-Sortどこでも読んでいます。それは問題ありませんが、なぜだけですか？なぜそうではないのですか、どちらも同様のパフォーマンスを持っていますか？多くの要素が事前に並べ替えられている場合にのみ便利ですが（ただし、その利点もあるはずです）、それ以外の場合は、他の2つよりも効率的である必要があります。QuicksortInsertion-SortInsertion-SortBubble-SortSelection-SortO(N^2)Insertion-SortBubble-Sort
そして第二に、このリンクでは、2番目の回答とそれに付随するコメントで、特定のまでO(N log N)と比較してパフォーマンスが低いと述べています。どうして？すべてのN>=2であるため、常にパフォーマンスが低下するはずです。O(N^2)NN^2N log NN > log N
分割統治クイックソートの各ブランチがしきい値に達したときにベイルアウトすると、データは次のようになります。
[the least 30-ish elements, not in order] [the next 30-ish ] ... [last 30-ish]
挿入ソートには、配列全体で1回だけ呼び出すことができるというかなり魅力的なプロパティがあり、30のブロックごとに1回呼び出す場合と基本的に同じように機能します。したがって、ループで呼び出す代わりに、それを最後に呼び出すオプション。これは、特にキャッシュを介してデータ全体を余分にプルするため、高速ではない可能性がありますが、コードの構造によっては便利な場合があります。
バブルソートも選択ソートもこの性質を持っていないので、答えは非常に単純に「便利」かもしれないと思います。誰かが選択ソートの方が良いのではないかと疑う場合、立証責任はそれがより速いことを「証明」することにあります。
この挿入ソートの使用にも欠点があることに注意してください。このようにすると、パーティションコードにバグがあり、要素が失われず、誤ってパーティション分割された場合、気付くことはありません。
編集：明らかに、この変更は、1975年にQuickSortで博士号を書いたSedgewickによるものです。最近、Musser（Introsortの発明者）によって分析されました。参照https://en.wikipedia.org/wiki/Introsort
Musserは、Sedgewickの遅延スモールソートのキャッシュへの影響も考慮しました。この場合、小さな範囲は、挿入ソートの1回のパスで最後にソートされます。彼は、キャッシュミスの数を2倍にすることができるが、両端キューでのパフォーマンスは大幅に向上し、テンプレートライブラリで保持する必要があると報告しました。これは、他の場合にソートをすぐに実行することによる利益が大きくなかったためです。
いずれにせよ、一般的なアドバイスは「何をするにしても、選択ソートを使わない」ということではないと思います。アドバイスは、「挿入ソートは、驚くほど小さくないサイズまでの入力でクイックソートに勝る」ということです。これは、クイックソートを実装しているときに自分自身に証明するのは非常に簡単です。同じ小さな配列で挿入ソートを明らかに打ち負かす別のソートを思いついた場合、それらの学術情報源のいずれも、それを使用しないように指示していません。驚きは、アドバイスが一貫して挿入ソートに向けられていることだと思います。各ソースが独自のお気に入りを選択するのではありません（入門教師は率直に言って驚くべきことです）バブルソートが好き-二度と聞いたことがなくてもかまいません）。挿入ソートは、一般的に小さなデータの「正しい答え」と考えられています。問題は、それが「速くあるべき」かどうかではなく、実際に速いかどうかであり、このアイデアを払拭するベンチマークに特に気づいたことはありません。
このようなデータを探す場所の1つは、ティムソートの開発と採用です。ティム・ピーターズが挿入を選んだ理由はかなり確かです。彼は一般的なアドバイスを提供していませんでした。彼は実際に使用するためにライブラリを最適化していたのです。
「ほぼ」ソートされたデータの挿入ソートが単純にはるかに高速であるという単純な事実について誰も言及していないことに驚いています。それが使用される理由です。
これは、挿入ソートがバブルソートよりも速いという経験的証拠です（30要素の場合、私のマシンでは、添付された実装で、javaを使用しています...）。
添付のコードを実行したところ、バブルソートは平均6338.515 nsで実行され、挿入には3601.0がかかったことがわかりました。
ウィルコクソンの符号付き検定を使用して、これが間違いであり、実際には同じである可能性を確認しましたが、結果は数値誤差の範囲を下回っています（事実上P_VALUE〜= 0）
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int j = i;
while (j > 0 && arr[j-1] > arr[j]) {
swap(arr, j, j-1);
j--;
}
}
}
public static void bubbleSort(int[] arr) {
for (int i = 0 ; i < arr.length; i++) {
boolean bool = false;
for (int j = 0; j < arr.length - i ; j++) {
if (j + 1 < arr.length && arr[j] > arr[j+1]) {
bool = true;
swap(arr,j,j+1);
}
}
if (!bool) break;
}
}
public static void main(String... args) throws Exception {
Random r = new Random(1);
int SIZE = 30;
int N = 1000;
int[] arr = new int[SIZE];
int[] millisBubble = new int[N];
int[] millisInsertion = new int[N];
System.out.println("start");
//warm up:
for (int t = 0; t < 100; t++) {
insertionSort(arr);
}
for (int t = 0; t < N; t++) {
arr = generateRandom(r, SIZE);
int[] tempArr = Arrays.copyOf(arr, arr.length);
long start = System.nanoTime();
insertionSort(tempArr);
millisInsertion[t] = (int)(System.nanoTime()-start);
tempArr = Arrays.copyOf(arr, arr.length);
start = System.nanoTime();
bubbleSort(tempArr);
millisBubble[t] = (int)(System.nanoTime()-start);
}
int sum1 = 0;
for (int x : millisBubble) {
System.out.println(x);
sum1 += x;
}
System.out.println("end of bubble. AVG = " + ((double)sum1)/millisBubble.length);
int sum2 = 0;
for (int x : millisInsertion) {
System.out.println(x);
sum2 += x;
}
System.out.println("end of insertion. AVG = " + ((double)sum2)/millisInsertion.length);
System.out.println("bubble took " + ((double)sum1)/millisBubble.length + " while insertion took " + ((double)sum2)/millisBubble.length);
}
private static int[] generateRandom(Random r, int size) {
int[] arr = new int[size];
for (int i = 0 ; i < size; i++)
arr[i] = r.nextInt(size);
return arr;
}
編集：
（1）バブルソートの最適化（上記で更新）により、バブルソートにかかる合計時間が6043.806に短縮され、大幅な変更を行うには不十分でした。ウィルコクソン検定はまだ決定的です：挿入ソートはより高速です。
（2）選択ソートテスト（コード添付）も追加し、挿入と比較しました。結果は次のとおりです。選択には4748.35がかかり、挿入には3540.114がかかりました。
ウィルコクソンのP_VALUEはまだ数値誤差の範囲を下回っています（事実上〜= 0）
使用される選択ソートのコード：
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length ; i++) {
int min = arr[i];
int minElm = i;
for (int j = i+1; j < arr.length ; j++) {
if (arr[j] < min) {
min = arr[j];
minElm = j;
}
}
swap(arr,i,minElm);
}
}
最初に簡単なのは、なぜ挿入ソートが選択ソートよりも優れているのかということです。挿入ソートは最適な入力シーケンスのためにO（n）にあるため、つまりシーケンスがすでにソートされている場合。選択ソートは常にO（n ^ 2）にあります。
なぜバブルソートよりも挿入ソートなのか？どちらも、すでにソートされている入力シーケンスに対して1回のパスしか必要としませんが、挿入ソートの方がパフォーマンスが低下します。より具体的には、挿入ソートは通常、バブルソートよりも少数の反転でパフォーマンスが向上します。ソースこれは、バブルソートがパスiのNi要素を常に反復するのに対し、挿入ソートは「検索」のように機能し、挿入を見つけるために平均して（Ni）/ 2要素（パスNi-1）を反復するだけでよいためです。ポジション。したがって、挿入ソートは平均して挿入ソートよりも約2倍高速であると予想されます。
編集： IVladがコメントで指摘しているように、選択ソートは任意のデータセットに対してn回のスワップのみ（したがって3n回の書き込みのみ）を行うため、スワップの数が少ないため、挿入ソートがそれを打ち負かす可能性はほとんどありませんが、実質的には実行される可能性があります比較が少ない。以下の理由は、バブルソートとの比較により適しています。バブルソートでは、同様の数の比較が行われますが、平均してより多くのスワップ（したがってより多くの書き込み）が行われます。
挿入ソートがバブルソートや選択ソートなどの他のO（n ^ 2）アルゴリズムよりも高速になる傾向がある理由のひとつは、後者のアルゴリズムでは、すべてのデータ移動にスワップが必要であり、これは最大3倍のメモリになる可能性があるためです。スワップのもう一方の端を後で再度スワップする必要がある場合は、必要に応じてコピーします。
挿入ソートOTOHを使用すると、次に挿入される要素がまだ最大の要素でない場合、一時的な場所に保存でき、右から開始して単一のデータコピーを使用することで（つまりスワップなしで）、すべての下位要素を前方にシャントします。 。これにより、元の要素を配置するためのギャップが開きます。
スワップを使用せずに整数を挿入ソートするためのCコード：
void insertion_sort(int *v, int n) {
int i = 1;
while (i < n) {
int temp = v[i]; // Save the current element here
int j = i;
// Shunt everything forwards
while (j > 0 && v[j - 1] > temp) {
v[j] = v[j - 1]; // Look ma, no swaps! :)
--j;
}
v[j] = temp;
++i;
}
}