ある日、大sorting日に、バブルの並べ替えとその修正に関する記事に触発されて、実装を作成し、それを改善する方法について考えました。 しかし同時に、私はまだJAVAの勉強を始めています（職業上、私はプログラマーではありませんが、少し書きました）。
最近、バブルソートが必要なのはなぜですか？
彼女は実際に最も遅いです。
彼女は最高（2次）複雑度アルゴリズムを持っています。
しかし！ 実装が最も簡単で非常に直感的で、教育目的やジュニア/インターンのインタビューでよく使用されます。
さらに、わずかな変更で、興味深い結果を得ることができます。
プログラミングの初心者で興味のある方は、猫の下でお願いします。
そのため、すぐにいくつかの目標を追求します。
古典的なバブルソートの実装を記述します。
古典的な「バブル」を追い越すはずの修正されたアルゴリズムを記述してください。
JAVAの基礎と少しのOOPを学んでください。
別のクラスArrayUtilsで並べ替えとその処理に関するすべての作業を実行し、 Runクラスから並べ替えメソッドを呼び出し、さまざまなデータセットで一連の呼び出しを形成します。
ArrayUtilsクラスには、次のものがあります。
- 配列自体
- 最も単純なメトリックとして、比較の数と値の移動の数、およびtimeAmount-操作時間-ソートメソッドの開始時に更新される2つの変数compareValueとswitchValueを追加します。
- 結果とメトリックス結果を出力する方法（）;
- ソートが実際に正しく機能するかどうかをすぐに確認する検証（）メソッド。
次の方法で検証を行いました。
ArrayUtilsクラスのコンストラクターは、入力として配列を受け取ります。この配列は 、 配列とsortArrayを2つのローカル配列にコピーします。後者は、通常のソーターArrays.sort（）によってすぐにソートされます。
クラスArrayUtils
public class ArrayUtils { final private int[] array; final private int[] sortedArray; long switchCount, compareCount, timeAmount; public ArrayUtils(int[] array) { this.array = array; this.sortedArray = Arrays.copyOf(array, array.length); Arrays.sort(sortedArray); } void results(String text) { System.out.println(String.format("%-35s Compares: %, 15d, Switches: %, 15d, Time: %, 15d", text, compareCount, switchCount, timeAmount)); } }
実際に、validation（）メソッドは、 配列の現在の状態を、通常のソーター（Javaではスマートクイックソートのバリエーションの1つ）でソートされたsortArrayと比較します。 私はアサートを通じてメソッドを呼び出しますが、Eclipseではデフォルトでオフになっていますが、 -eaオプションを追加すると、配列が破損した場合にアサートが正しく抜けます。
検証方法
boolean validate() { if (Arrays.equals(array,sortedArray)) return true; return false; }
これで、バブルソートの実装を開始できます。これは、今後の作業の標準になります。
sortBubbleClassic
public void sortBubbleClassic() { int currentPosition; int maxPosition; int temp; switchCount=0; compareCount=0; time = System.nanoTime(); for (maxPosition=array.length - 1; maxPosition >= 0;maxPosition--) { for (currentPosition = 0; currentPosition < maxPosition; currentPosition++) { compareCount++; if (array[currentPosition] > array[currentPosition+1]) { temp = array[currentPosition]; array[currentPosition] = array[currentPosition+1]; array[currentPosition+1] = temp; switchCount++; } } } time = System.nanoTime() - time; assert(validate()); return; }
次に、ソートを呼び出すRunクラスを作成し、そこにfillRandom（）メソッドを追加して、さらにソートするためのランダムデータセットを作成します。
Run.java
public class Run { static public void FillRandom(int[] array) { for (int count=0; count < array.length; count++) { array[count] = (int)(Math.random()*100); } } public static void main(String[] args) { int arraySize= 10000; int random[] = new int[arraySize+1]; FillRandom(random); ArrayUtils bubbleClassic = new ArrayUtils(random); bubbleClassic.sortBubbleClassic(); bubbleClassic.results("Bubble Classic, random array"); } }
実行できます。 作成したクラスに配列を渡し、それをコピーして、ランダムデータを含む元の配列が将来の使用のために変更されないようにしました。 そのため、さまざまな方法でランダムデータの同一セットをソートできます。
実行すると、結果が得られます。
Bubble Classic, random array Compares: 50 005 000, Switches: 24 486 908, Time: 117 116 326
assertがエラーをスローしない場合、アルゴリズムは正しくソートされます。 10,000個の要素の配列で、5,000万件を超える比較と2,400万件の順列を受け取りました。
sortBubbleClassicメソッドをsortBubbleAdvancedにコピーし、改善できる点を考え始めます。
まず、配列を無駄にしないように配列が並べ替えられているかどうかを確認するチェックを追加できると考えました。
これを行うために、内側のループの開始前にfalseに設定されたブール変数changedを作成しました。ループ内では、置換を行うとtrueに設定されます 。
内側のサイクル全体を実行した後、単一の順列を実行していない場合、さらにサイクルを無駄に駆動することはできませんが、すぐに終了します。
sortBubbleAdvanced-ステップ1
public void sortBubbleClassic() { int currentPosition; int maxPosition; int temp; switchCount=0; compareCount=0; timeAmount = System.nanoTime(); Boolean changed; // for (maxPosition=array.length - 1; maxPosition >= 0;maxPosition--) { changed=false; // for (currentPosition = 0; currentPosition < maxPosition; currentPosition++) { compareCount++; if (array[currentPosition] > array[currentPosition+1]){ temp = array[currentPosition]; array[currentPosition] = array[currentPosition+1]; array[currentPosition+1] = temp; switchCount++; changed = true; // } } if (!changed) { // - timeAmount = System.nanoTime() - timeAmount; assert(validate()); return; } } timeAmount = System.nanoTime() - timeAmount; assert(validate()); return; }
さらに、配列の先頭に大きな数がある場合、それを右に引き出して、多数の順列を作成します。 すぐに配列の末尾に移動できるのは論理的です。
しかし、投げる場所を正確に見つけるために多くのチェックを行うことは有益ではありません。 したがって、私は最も簡単な解決策を作成しました-現在の値が右端の要素の値よりも大きいかどうかを確認します-それらを交換します。 チェックの数を増やしますが、順列の数は減らします。
すぐに2番目の最適化-配列の最後に小さな数がある場合、通常は、配列内の要素の数にほぼ等しいN個の内部ループを介して配列の先頭まで実行されます。 したがって、現在の値と配列内の左端の値が小さい場合は、スワップするためにもう1つチェックを追加します。 それ自体では、このアクションは追加のチェックを行いますが、わずかに加速します。 しかし、内側のループの実行を完了した後、データ配列の左端の位置に最小数があることを確認できます。 これは、最初の要素からではなく、2番目の要素から内側のサイクルを開始できることを意味します。 各ステップで、内側のループの配列を左右の2つの値で同時にトリミングします。 これは明らかな増加です。
3つのチェックを合理的に配置します。
最初のチェックはメインバブルです。2つの要素が比較され、次に、現在の要素と配列の一番左の要素が比較されます。 それから一番右のもので、誰が大きいかというテーマで。
sortBubbleAdvanced-ステップ2
public void sortBubbleAdvanced(){ int currentPosition; int maxPosition; // int minPosition = 0; // boolean changed; // , int temp; switchCount = 0; compareCount = 0; timeAmount = System.nanoTime(); for (maxPosition = array.length - 1; maxPosition >= 0; maxPosition--) { changed=false; for (currentPosition = minPosition; currentPosition < maxPosition; currentPosition++) { if (array[currentPosition] > array[currentPosition+1]){ // temp = array[currentPosition+1]; array[currentPosition+1] = array[currentPosition]; array[currentPosition] = temp; switchCount++; changed=true; } if (array[currentPosition] < array[minPosition]){ // temp = array[minPosition]; array[minPosition] = array[currentPosition]; array[currentPosition] = temp; switchCount++; changed=true; } if (array[currentPosition] > array[maxPosition]){ // temp = array[maxPosition]; array[maxPosition] = array[currentPosition]; array[currentPosition] = temp; switchCount++; changed=true; } compareCount+=3; } if (!changed) { timeAmount=System.nanoTime()-timeAmount; assert(validate()); return; } compareCount++; minPosition++ // } timeAmount=System.nanoTime()-timeAmount; assert(validate()); return; }
何が起こったのかを確認できます。 Runクラスを編集して、2つのメソッドのテストを追加して実行します
Bubble Classic, random array Compares: 50 005 000, Switches: 24 758 509, Time: 105 797 881 Bubble Advanced, random array Compares: 112 317 213, Switches: 18 684 909, Time: 87 415 460
ご覧のとおり、結果は非常に重要です。 比較の数は2倍以上になりました。 しかし、一方で、順列の数は減少し、それらは時間的に「より高価」であるため、やがて約15％を獲得します！..
さらに2つのデータセットを追加します-すでにソートされたインクリメンタル配列、逆順でソート- デクリメンタル （理論的にはソートの最悪のケースであるべきです）、それらをRunクラスに追加し、3つの配列すべてに対してsortBubbleClassicとsortBubbleAdvanced呼び出しを追加します- ランダム 、 インクリメンタルそして減少
さらに2種類の配列
static public void fillDecremental(int[] array) { for (int count=0; count < array.length; count++) { array[count] = array.length-count; } } static public void fillIncremental(int[] array) { for (int count=0; count < array.length; count++) { array[count] = count; } }
結果を確認します。
Bubble Classic, random array Compares: 50 005 000, Switches: 24 678 169, Time: 116 314 053 Bubble Advanced, random array Compares: 111 879 748, Switches: 18 615 013, Time: 77 282 419 Bubble Classic, decremental array Compares: 50 005 000, Switches: 50 005 000, Time: 48 202 818 Bubble Advanced, decremental array Compares: 112 527 500, Switches: 49 985 004, Time: 77 115 071 Bubble Classic, incremental array Compares: 50 005 000, Switches: 0, Time: 24 805 261 Bubble Advanced, incremental array Compares: 30 000, Switches: 0, Time: 35 084
ランダムなデータセットでは、高度な方法が勝つと予想され、デクリメンタルではほぼ60％長くなります;（
ただし、変数changedを使用した小さなチェックのおかげで、既にソートされた配列をただちにチェックします。
私はこの結果に一部だけ満足していました。 一部のセットで元の結果よりも悪い結果を示す可能性がある場合、アルゴリズムの最適化を終了することはできません。 基本原則を変更せずにバブルの並べ替えを改善する方法を考えると、「バブル」では、内側のサイクルの各パスで最大数がアクティブに移動し、最大数もそこに移動することに気付きました。 したがって、配列の右辺は左辺の前にソートされます...このアイデアは次のアイデアで実現されました。
各順列で、この位置を覚えています。 内側のループの最後の要素に到達すると、右側の配列を1つ減らすことはできませんが、順列があったこの最後の位置にすぐにトリミングできます。
サイクル数は大幅に削減する必要があります。デクリメント配列の場合は少なくとも約半分です。
これはわずか3行で実装されます。
sortBubbleAdvanced-最終ステップ
public void sortBubbleAdvanced(){ int currentPosition; int maxPosition; int changedMaxPosition = array.length - 1; // int minPosition = 0; boolean changed; int temp; switchCount = 0; compareCount = 0; timeAmount = System.nanoTime(); for (maxPosition = array.length - 1; maxPosition >= 0; minPosition++) // , minPosition++ { changed=false; for (currentPosition = minPosition; currentPosition < maxPosition; currentPosition++) { if (array[currentPosition] > array[currentPosition+1]){ temp = array[currentPosition+1]; array[currentPosition+1] = array[currentPosition]; array[currentPosition] = temp; switchCount++; changed=true; changedMaxPosition = currentPosition; // } if (array[currentPosition] < array[minPosition]){ temp = array[minPosition]; array[minPosition] = array[currentPosition]; array[currentPosition] = temp; switchCount++; changed=true; } if (array[currentPosition] > array[maxPosition]){ temp = array[maxPosition]; array[maxPosition] = array[currentPosition]; array[currentPosition] = temp; switchCount++; changed=true; } compareCount+=3; } if (!changed) { timeAmount=System.nanoTime()-timeAmount; assert(validate()); return; } compareCount++; maxPosition = changedMaxPosition; // - } timeAmount=System.nanoTime()-timeAmount; assert(validate()); return; }
何が起こったのか見てみましょう：
Bubble Classic, random array Compares: 50 005 000, Switches: 25 020 725, Time: 117 550 372 Bubble Advanced, random array Compares: 45 090 482, Switches: 10 174 100, Time: 70 032 156 Bubble Classic, decremental array Compares: 50 005 000, Switches: 50 005 000, Time: 47 815 033 Bubble Advanced, decremental array Compares: 60 022 000, Switches: 30 003 000, Time: 46 042 519 Bubble Classic, incremental array Compares: 50 005 000, Switches: 0, Time: 25 072 582 Bubble Advanced, incremental array Compares: 30 000, Switches: 0, Time: 34 773
約10％増加し、ランダムデータの並べ替えを高速化し、デクリメント配列のYESをわずかなマージンで加速しましたが、従来の「バブル」を追い越しました-予想どおり、時間は約半分に減少しました。
増分配列は即座に渡されます。
すでに並べ替えられた部分の空のパスが大幅に削減されたため、高度なアルゴリズムのチェックの数が減り、場合によっては元のアルゴリズムよりもさらに少なくなり、順列の数は常にはるかに少なくなります（チェックを除き、空のパスが配列を通過するだけのコストです）。
そのため、バブルソートの主要なアイデアの範囲内で、結果を大幅に改善することができました。
さらに何ができますか？
アルゴリズムをクイックソートリーダーと比較しましょう。
私たちは簡単な実装を書いています（正直なところ、私はインターネット上でそれを盗み、メトリクスが残るように微調整しましたが、 クイックソートが再帰を使用することを考えると、メトリクスを追加するのが良いでしょう...しかし、それを再帰なしでアルゴリズムと比較する方法は？ポイントではない...）、だから：
簡単なクイックソート実装
public void quickSort() { timeAmount = System.nanoTime(); switchCount = 0; compareCount = 0; doQuickSort(0, array.length - 1); timeAmount = System.nanoTime() - timeAmount; assert(validate()); } private void doQuickSort(int startPosition, int lastPosition) { if (startPosition >= lastPosition) { compareCount++; return; } int tempStartPosition = startPosition, tempLastPosition = lastPosition; int currentPosition = tempStartPosition - (tempStartPosition - tempLastPosition) / 2; while (tempStartPosition < tempLastPosition) { while (tempStartPosition < currentPosition && (array[tempStartPosition] <= array[currentPosition])) { compareCount++; tempStartPosition++; } while (tempLastPosition > currentPosition && (array[currentPosition] <= array[tempLastPosition])) { compareCount++; tempLastPosition--; } if (tempStartPosition < tempLastPosition) { int temp = array[tempStartPosition]; array[tempStartPosition] = array[tempLastPosition]; array[tempLastPosition] = temp; switchCount++; if (tempStartPosition == currentPosition) currentPosition = tempLastPosition; else if (tempLastPosition == currentPosition){ currentPosition = tempStartPosition; compareCount++; } compareCount++; } compareCount++; } doQuickSort(startPosition, currentPosition); doQuickSort(currentPosition + 1, lastPosition); }
結果を確認します。
Bubble Classic, random array Compares: 50 005 000, Switches: 24 684 713, Time: 117 338 627 QuickSort, random array Compares: 453 318, Switches: 22 234, Time: 3 000 141 Bubble Advanced, random array Compares: 44 832 715, Switches: 10 048 493, Time: 70 540 407 Bubble Classic, decremental array Compares: 50 005 000, Switches: 50 005 000, Time: 47 269 214 QuickSort, decremental array Compares: 153 632, Switches: 5 000, Time: 179 766 Bubble Advanced, decremental array Compares: 60 022 000, Switches: 30 003 000, Time: 45 579 908 Bubble Classic, incremental array Compares: 50 005 000, Switches: 0, Time: 24 927 899 QuickSort, incremental array Compares: 143 632, Switches: 0, Time: 134 437 Bubble Advanced, incremental array Compares: 30 000, Switches: 0, Time: 35 394
予想どおり、 クイックソートはランダムデータセットとデクリメント配列の両方で簡単にすべてのアルゴリズムを実行します。 しかし、突然、既に並べ替えられた配列では、高度なバブルによってほぼ4倍高速になりました！
最初は、これにはあまり意味がないと思いました。 ええ、はい、私の高度なアルゴリズムは、配列が既により速くソートされていることをチェックしますが、そのようなタスクは非常にまれです。
それから、これがすべてではないことを理解しました-実際、ほぼ同じ速度で、高度なアルゴリズムは一度に最大3つの数値（最小、最大、および途中でさらに数個）をソートでき、チェックすることにしました練習。
増分配列を作成する方法を変更して、ソートされた配列の中央にいくつかの乱数があるようにしました。
絶対にソートされていない配列を作成します
static public void fillIncremental(int[] array) { for (int count=0; count < array.length; count++) { array[count] = count; } for (int count=array.length/2; count < array.length/2+5; count++) // 5 array[count]=(int)Math.random()*100; }
何が起こったのか見てみましょう：
Bubble Classic, incremental array Compares: 50 005 000, Switches: 24 995, Time: 24 751 238 QuickSort, incremental array Compares: 219 964, Switches: 8 426, Time: 249 624 Bubble Advanced, incremental array Compares: 179 740, Switches: 24 981, Time: 125 123
高度なバブルアルゴリズムはクイックソートよりも高速に処理され、5つの乱数をほぼ2倍の速さでソートしました。
配列のサイズを10倍に増やし、念のためチェックします。
Bubble Classic, incremental array Compares: 5 000 050 000, Switches: 249 995, Time: 2 168 664 535 QuickSort, incremental array Compares: 2 539 530, Switches: 86 062, Time: 11 479 582 Bubble Advanced, incremental array Compares: 1 799 740, Switches: 249 981, Time: 6 411 974
とにかく、ほぼ2倍の速度です。
並べ替えられていない要素の数が特定の最小量を超えない、ほとんど並べ替えられた配列では、再設計されたバブルアルゴリズムは2次の複雑さを示しませんが、通常のO（N）であり、実装が容易なため、クイックソートをバイパスします。
ソートされていない要素の数を約10に追加すると、クイックソートとbubbleAdvancedの速度が比較され、その後、アルゴリズムがクラッシュして絶望的な2次スローネスになります。 それにもかかわらず、事前に並べ替えられたデータ配列にランダムに挿入されたいくつかの値を並べ替える必要がある場合、それは競合の対象外です。
道徳、結果、結論。
結果 、または数値を上に示しましたが、コメントで議論できます。
ソース-githubで入手できます（ごみが少しありますが、mavenを学ぼうとしましたが、ソースクラスファイルは任意のIDEまたはコンソールでコンパイルできます）。
さらに、HelloWorldよりも少し複雑な最初のJAVAコードを書きました。 また、内部から少なくとも2つのソート方法を学びました。
さらに、アルゴリズムをさらに深く掘り下げると、どのような結果が期待でき、どこを掘るかを直感的に推測できます。
これまでのところ、減分された配列がランダムよりも高速に処理される理由はよくわかりません。 バブルソートの最悪のケースはデクリメンタル配列であるように思えました。 おそらくこれは、ランダムな配列には同一の数値が存在するという事実によるものであり、一般的にはまだ考慮すべきことがあります。
結論と道徳 -特定のデータセットについて、速度が重要な場合、通常の方法を追い越すことができる独自の自転車を考えて考えることは常に理にかなっています。その主なタスクは、最も一般的なケースで高速な結果を示すことです。