Javaでのバブルソートの実装

非常に多くの並べ替えアルゴリズムがあり、その多くは非常に特殊で、狭い範囲の問題を解決し、特定の種類のデータを処理するために開発されました。しかし、この多様性の中で最も単純なアルゴリズムは当然のことながらバブルソートであり、これはどのプログラミング言語でも実装できます。その単純さにもかかわらず、多くのかなり複雑なアルゴリズムの基礎となっています。もう 1 つの同様に重要な利点は、そのシンプルさです。したがって、追加の文献を用意しなくても、すぐに覚えて実装することができます。 Java でのバブルソートの実装 - 1

導入

現代のインターネット全体は、データベースに収集された膨大な数の異なるタイプのデータ構造で構成されています。ユーザーの個人データから高度にインテリジェントな自動化システムのセマンティックコアに至るまで、あらゆる種類の情報が保存されます。言うまでもなく、この膨大な構造化情報において、データの分類は非常に重要な役割を果たします。並べ替えは、データベース内の情報を検索する前に必須の手順となる場合があり、並べ替えアルゴリズムの知識はプログラミングにおいて非常に重要な役割を果たします。

機械の目と人間の目による選別

高さの異なる 5 つの列を昇順に並べ替える必要があると想像してください。これらの列は、あらゆる種類の情報 (株価、通信チャネルの帯域幅など) を意味する可能性があり、より明確にするために、このタスクの独自のバージョンをいくつか提示することができます。たとえば、アベンジャーズを身長順に並べ替えます。

コンピュータプログラムとは異なり、全体像を把握でき、身長による並べ替えを正常に完了するにはどのヒーローをどこに移動する必要があるかをすぐに把握できるため、並べ替えは難しくありません。おそらくすでにお気づきかと思いますが、このデータ構造を昇順に並べ替えるには、ハルクとアイアンマンの位置を入れ替えるだけで十分です。

終わり！

これでソートは正常に完了します。ただし、コンピュータはあなたとは異なり、~~やや愚かで~~、データ構造全体を全体として認識しません。その制御プログラムは一度に 2 つの値しか比較できません。この問題を解決するには、2 つの数値をメモリに入れて比較演算を実行し、次に別の数値のペアに移るということを、すべてのデータが分析されるまで繰り返す必要があります。したがって、並べ替えアルゴリズムは次の 3 つのステップの形で非常に簡素化できます。

2 つの要素を比較します。
そのうちの 1 つを交換またはコピーします。
次の要素に移動します。

アルゴリズムが異なれば、これらの操作をさまざまな方法で実行できますが、次にバブルソートがどのように機能するかを検討していきます。

バブルソートアルゴリズム

バブルソートが最も簡単だと考えられていますが、このアルゴリズムを説明する前に、機械のように 1 つの期間内に 2 人のヒーローのみを相互に比較できる場合、アベンジャーズを身長によってどのようにソートするかを想像してみましょう。最も可能性が高いのは、次のとおりです (最も最適な方法です)。

配列 (Black Widow) の要素 0 に移動します。
ゼロの要素 (ブラックウィドウ) と最初の要素 (ハルク) を比較します。
位置 0 の要素の方が高い場合は、それらを交換します。
それ以外の場合、位置 0 の要素の方が小さい場合は、その要素をその場所に残します。
右の位置に移動して比較を繰り返します (ハルクとキャプテンを比較)

このようなアルゴリズムを使用して 1 回のパスでリスト全体を調べても、並べ替えは完全には完了しません。しかしその一方で、リスト内の最大の要素は右端の位置に移動されます。最大の要素を見つけるとすぐに、それを最後に移動するまで常に場所を変更することになるため、これは常に発生します。つまり、プログラムは配列内でハルクを「見つける」とすぐに、彼をリストの最後に移動します。

これが、このアルゴリズムがバブルソートと呼ばれる理由です。その操作の結果、リスト内の最大の要素が配列の一番上に配置され、それより小さい要素はすべて 1 つ左にシフトされるからです。

並べ替えを完了するには、配列の先頭に戻り、上記の 5 つの手順を再度繰り返し、左から右に移動し、必要に応じて要素を比較および移動する必要があります。ただし、今回は、最大の要素 (ハルク) が絶対的に右端の位置にあることがすでにわかっているため、配列の終わりの 1 要素手前でアルゴリズムを停止する必要があります。

したがって、プログラムには 2 つのループが必要です。より明確にするために、プログラムコードの確認に進む前に、次のリンクでバブルソートの仕組みを視覚化して確認できます。バブルソートの仕組みの視覚化

Javaでのバブルソートの実装

Java でソートがどのように機能するかを示すために、次のプログラムコードを示します。

5 つの要素の配列を作成します。
アベンジャーズの台頭をそこにアップロードします。
配列の内容を表示します。
バブルソートを実装します。
ソートされた配列を再表示します。

以下のコードを表示したり、お気に入りの~~IntelliJ~~ IDE にダウンロードしたりすることもできます。以下で分析します。

class ArrayBubble{
    private long[] a;   // array reference
    private int elems;  //number of elements in the array

    public ArrayBubble(int max){    //class constructor
        a = new long[max];          //create an array with size max
        elems = 0;                  //when created, the array contains 0 elements
    }

    public void into(long value){   // method for inserting an element into an array
        a[elems] = value;           //insert value into array a
        elems++;                    //array size increases
    }

    public void printer(){          // method for outputting an array to the console
        for (int i = 0; i < elems; i++){    //for each element in the array
            System.out.print(a[i] + " ");   // output to console
            System.out.println("");         //a new line
        }
        System.out.println("----End array output----");
    }

    private void toSwap(int first, int second){ //method swaps a pair of array numbers
        long dummy = a[first];      // put the first element into a temporary variable
        a[first] = a[second];       // put the second element in place of the first
        a[second] = dummy;          //instead of the second element, write the first from temporary memory
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Outer loop
            for (int in = 0; in < out; in++){       //Inner loop
                if(a[in] > a[in + 1])               //If the order of the elements is wrong
                    toSwap(in, in + 1);             // call the swapping method
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Create array array with 5 elements

        array.into(163);       //fill the array
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //display elements before sorting
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // print the sorted list again
    }
}

コードには詳細なコメントが含まれていますが、プログラムで示されるメソッドの一部についても説明します。プログラムの主な作業を実行する主要なメソッドは、ArrayBubble クラスに記述されます。このクラスにはコンストラクターといくつかのメソッドが含まれています。

into– 要素を配列に挿入する方法。
printer– 配列の内容を行ごとに表示します。
toSwap– 必要に応じて要素を再配置します。これを行うには、一時変数が使用されdummy、最初の数値の値が書き込まれ、最初の数値の代わりに 2 番目の数値の値が書き込まれます。次に、一時変数の内容が 2 番目の数値に書き込まれます。これは 2 つの要素を交換するための標準的な手法です。

そして最後にメインメソッド:

bubbleSorter– これは主な作業を行い、配列に格納されたデータを並べ替えます。これについては、もう一度個別に説明します。

public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
    for (int out = elems - 1; out >= 1; out--){  //Outer loop
        for (int in = 0; in < out; in++){       //Inner loop
            if(a[in] > a[in + 1])               //If the order of the elements is wrong
                toSwap(in, in + 1);             // call the swapping method
        }
    }
}

outここでは、外部と内部の2 つのカウンタに注意する必要がありますin。 外部カウンターはout配列の末尾から値の列挙を開始し、新しいパスが発生するたびに徐々に 1 ずつ減少します。out新しいパスを実行するたびに、配列の右側にすでに並べ替えられている値に影響を与えないように、変数はさらに左にシフトされます。内部カウンターはin配列の先頭から値の列挙を開始し、新しいパスごとに徐々に 1 ずつ増加します。増加は、(現在のパスで最後に分析された要素)inに達するまで発生します。out内側のループはin2 つの隣接するセルinとを比較しますin+1。inより大きい数値がに格納されている場合in+1、メソッドが呼び出されtoSwap、これら 2 つの数値の位置が交換されます。

結論

バブルソートアルゴリズムは最も遅いアルゴリズムの 1 つです。配列が N 個の要素で構成されている場合、最初のパスでは N-1 個の比較が実行され、2 番目のパスでは N-2 個の比較が実行され、その後は N-3 個の比較が実行されます。つまり、パスの合計数は次のようになります: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 したがって、ソート時のアルゴリズムは次のようになります。約 0.5x(N ^2) の比較を実行します。N = 5 の場合、比較の数は約 10 になり、N = 10 の場合、比較の数は 45 に増加します。したがって、要素の数が増加するにつれて、並べ替えの複雑さは大幅に増加します。

アルゴリズムの速度は、パスの数だけでなく、実行する必要がある置換の数にも影響されます。ランダムデータの場合、順列数の平均は (N^2) / 4 で、これはパス数の約半分です。ただし、最悪の場合、順列の数が N^2 / 2 になる可能性もあります。これは、データが最初に逆順に並べ替えられている場合に当てはまります。これはかなり遅い並べ替えアルゴリズムであるという事実にもかかわらず、その仕組みを知り理解することは非常に重要であり、前述したように、より複雑なアルゴリズムの基礎となります。ジグド！

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION