Bubbleソートアルゴリズム Java: 配列ソートプログラムと例

何ですか Bubble ソート?

BubbleSortは、配列の最初の要素と次の要素を比較する、単純な比較ベースのソートアルゴリズムです。配列の現在の要素が次の要素よりも数値的に大きい場合、要素が交換されます。同様に、このアルゴリズムは配列のすべての要素を走査します。

このアルゴリズムは、未ソート領域で最大の値が、まるで水面に浮かぶ泡のように、最終位置まで着実に上昇していく様子からその名が付けられました。最初の処理が完了すると、最大の要素が最後のインデックスに配置されます。2回目の処理が完了すると、2番目に大きい要素が固定され、配列が完全にソートされるまでこのプロセスが繰り返されます。

この記事では、 Java 実施するプログラム Bubble. ソート。プログラムロジックを理解するのに役立つコードの出力を確認し、その後、最適化されたバージョンとそれに続く複雑性分析を確認してください。

どのように Bubblソートアルゴリズムは機能しますか？

Bubblソートは配列を繰り返し走査することで機能します。各走査では、最初のインデックスから現在ソートされていない領域の末尾まで移動し、隣接する値を比較して交換します。ping それらが間違った順序で出現した場合は、それらを削除します。残っている値の中で最大の値は常に未ソート領域の右端に移動するため、処理ごとに領域はちょうど1つずつ縮小します。

このプロセス全体は、繰り返し可能な4つのステップに分解できます。

1. 比較： インデックス j-1 の要素をインデックス j の要素と比較します。
2. スワップ： 左側の要素が右側の要素より大きい場合は、一時変数を使用して2つの値を交換します。
3. 前進： 右に1つ移動し、未ソート領域の端に到達するまでこれを繰り返します。
4. 繰り返す： 要素が1つ少ない領域に対して新しいパスを開始し、n-1回のパス後、またはパスでスワップが行われなくなった時点で停止します。

下の表 tracこれは、このページの後半で説明するプログラムで使用されるサンプル配列 {860, 8, 200, 9} です。これは、各パスの最後にどの値が最終位置に落ち着くかを正確に示しています。

3回目のパスでは比較は行われますが、スワップは行われません。最適化された実装ではこの条件を検知して即座に停止します。これは、このアルゴリズムに適用できる最も価値のある改善点です。

Bubblソートアルゴリズムの擬似コード

書く前に Java 構文を使うことで、言語に依存しない擬似コードでロジックを表現するのに役立ちます。以下のバージョンには早期終了フラグが含まれているため、従来の動作と最適化された動作の両方に対応しています。

procedure bubbleSort(array A, integer n)
    for i from 0 to n - 2 do
        swapped := false
        for j from 1 to n - i - 1 do
            // compare the adjacent pair
            if A[j - 1] > A[j] then
                swap A[j - 1] and A[j]
                swapped := true
            end if
        end for
        // no swap in a full pass means the array is sorted
        if swapped = false then
            break
        end if
    end for
end procedure

外側のループはパスの回数を制御し、内側のループは1回のパス内の比較回数を制御します。最後の i 個の位置には既に最終値が格​​納されているため、内側のループの上限は n – i – 1 となります。

Java 実施プログラム Bubble 並べ替え

以下のプログラムは整数配列を昇順にソートします。ループ内に余分なprint文を意図的に残しているのは、パスごとの読み取りが trace は、初心者がスワップがどのように蓄積されるかを理解するための最も手っ取り早い方法です。

package com.guru99;

public class BubbleSort {

    public static void main(String[] args)
    {
        int arr[] = {860, 8, 200, 9};

        System.out.println("---Array BEFORE Bubble Sort---");

        printArray(arr);

        bubbleSort(arr); //sorting array elements using bubble sort

        System.out.println("---Array AFTER Bubble Sort---");

        printArray(arr);

    }

    static void bubbleSort(int[] array)
    {
        int n = array.length;
        int temp = 0;
        for(int i = 0; i < n; i++) // Looping through the array length
        {   System.out.println("Sort Pass Number " + (i + 1));
            for(int j = 1; j < (n - i); j++)
            {
                System.out.println("Comparing " + array[j - 1] + " and " + array[j]);
                if(array[j - 1] > array[j])
                {
                    //swap elements
                    temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    System.out.println(array[j] + " is greater than " + array[j - 1]);
                    System.out.println("Swapping Elements: New Array After Swap");
                    printArray(array);
                }

            }
        }

    }

    static void printArray(int[] array){

        for(int i = 0; i < array.length; i++)
        {
            System.out.print(array[i] + " ");
        }
        System.out.println();

    }
}

出力：

---Array BEFORE Bubble Sort---
860 8 200 9
Sort Pass Number 1
Comparing 860 and 8
860 is greater than 8
Swapping Elements: New Array After Swap
8 860 200 9
Comparing 860 and 200
860 is greater than 200
Swapping Elements: New Array After Swap
8 200 860 9
Comparing 860 and 9
860 is greater than 9
Swapping Elements: New Array After Swap
8 200 9 860
Sort Pass Number 2
Comparing 8 and 200
Comparing 200 and 9
200 is greater than 9
Swapping Elements: New Array After Swap
8 9 200 860
Sort Pass Number 3
Comparing 8 and 9
Sort Pass Number 4
---Array AFTER Bubble Sort---
8 9 200 860

Code 説明： その バブルソート メソッドは配列を参照渡しで受け取るため、呼び出し元は戻り値なしでソートされた結果を見ることができます。 一時 3行のスワップ中は1つの値を保持するため、アルゴリズムに必要な追加メモリはO(1)だけです。 n – i 内側のループ条件では、既にソートされた末尾の位置が二度と訪問されないことが保証されます。

最適化 Bubbleソートプログラム Java

上記のプログラムは、配列が早期にソートされた場合でも、常にn-1回のパスを実行します。ブール型のフラグを1つ追加することで、この非効率性を解消できます。1回のパスがスワップなしで完了した場合、配列は確実にソートされているため、外側のループはすぐに停止できます。

package com.guru99;

public class OptimizedBubbleSort {

    public static void main(String[] args) {
        int arr[] = {5, 12, 33, 47, 58};
        bubbleSort(arr);
        System.out.println(java.util.Arrays.toString(arr));
    }

    static void bubbleSort(int[] array) {
        int n = array.length;
        int passes = 0;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 1; j < n - i; j++) {
                if (array[j - 1] > array[j]) {
                    int temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    swapped = true;
                }
            }
            passes++;
            // Early exit: the array is already sorted
            if (!swapped) {
                break;
            }
        }
        System.out.println("Passes executed: " + passes);
    }
}

出力：

Passes executed: 1
[5, 12, 33, 47, 58]

入力配列は既にソートされていたため、最適化されたバージョンは4回のパスではなく1回のパスで完了しました。ほぼソートされたデータの場合、この変更によりワークロードが2次からほぼ線形に変化します。これが主な理由です。 Bubbleソートは、実際のコードの中にも時折登場します。

時間計算量と空間計算量 Bubble 並べ替え

複雑性とは、入力サイズが大きくなるにつれて実行時間がどのように増加するかを表します。 Bubble 最適化されていないバージョンでの比較回数は n(n-1)/2 に固定されており、これは確実に二次クラスに属します。

すべての交換は元の配列内で行われ、一時変数は 1 つしか使用されないため、 Bubbleソートは、O(1)の補助空間を必要とするインプレースアルゴリズムです。また、安定ソートでもあり、同じキーを持つ2つのレコードは、ソート後も元の相対的な順序を維持します。

の長所と短所 Bubble 並べ替え

両方の側面を理解することで、アルゴリズムが許容できる選択肢である場合と、置き換えるべき場合を判断するのに役立ちます。

優位性

• シンプルさ： その論理はおよそ10行に収まるため、面接の場で正確に記述しやすい。
• 現場での運用： 補助配列は割り当てられないため、メモリ使用量は入力サイズに応じて増加しません。
• 安定性： 同じキーは元の順序を保持するため、二次フィールドでレコードをソートする際に重要となる。
• 早期離脱検知： スワップされたフラグは、一度の処理で既にソート済みの配列を識別します。

デメリット

• 二次成長： 10,000万個の要素をソートするには、最悪の場合、約50万回の比較が必要となる。
• 過剰な書き込み: このアルゴリズムは選択ソートよりもはるかに多くのスワップを実行するため、メモリを大量に消費し、書き込み操作も遅くなる。
• スケーラビリティが低い: 実際の運用環境では、ほとんどの場合、クイックソート、マージソート、または組み込みのArrays.sortメソッドが好まれます。

Bubbleソートとその他のソート方法 Algorithms

下の表は比較 Bubble 次に初心者が学ぶ並べ替えテクニックを使って並べ替えを行い、それぞれのテクニックがどこで最も優れているかを正確に把握しましょう。

Bubble ソートと挿入ソートは線形ベストケースを共有しますが、挿入ソートは部分的にソートされたデータに対してより少ないスワップを実行します。選択ソートは常に正確に n-1 回のスワップを実行するため、trac書き込みコストが高い場合は、安定性を犠牲にするものの、有効な選択肢となります。数百要素を超える配列の場合は、クイックソートまたはヒープソートが適切な選択肢です。

ここで使用されている配列走査パターンに慣れたら、次のような多くの古典的な演習で同じループ構造が現れます。 フィボナッチ数列 Java Java 回文プログラム. Rev見る Java アレイ そしてより広い Java チュートリアル これは、このアルゴリズムが依存する基礎を強化するだろう。

よくあるご質問