Javaでのバブルソート

投稿日: 2019-10-18 2022-11-01
タグ: Algorithms, Java

1. 序章

この簡単な記事では、Javaの実装に焦点を当てて、バブルソートアルゴリズムについて詳しく説明します。

これは、最も簡単な並べ替えアルゴリズムの1つです。基本的な考え方は、コレクションが並べ替えられるまで、配列の隣接する要素が間違った順序である場合、それらを交換し続けることです。

データ構造を繰り返すと、小さなアイテムがリストの一番上に「バブル」します。したがって、この手法はバブルソートとして知られています。

並べ替えはスワッピングで行われるため、インプレース並べ替えと言えます。

また、 2つの要素の値が同じ場合、結果のデータの順序は保持されます。これにより、安定ソートになります。

2. 方法論

前述のように、配列を並べ替えるには、隣接する要素を比較しながら配列を反復処理し、必要に応じてそれらを交換します。サイズがnの配列の場合、n-1のような反復を実行します。

方法論を理解するために例を取り上げましょう。配列を昇順で並べ替えます。

4 2 1 6 3 5

最初の反復は、4と2を比較することから始めます。それらは間違いなく正しい順序ではありません。交換すると、次のようになります。

[2 4] 1 6 3 5

ここで、4と1について同じことを繰り返します。

2 [1 4] 6 3 5

私たちは最後までそれを続けます：

2 1 [ 4 6] 3 5

2 1 4 [3 6] 5

2 1 4 3 [5 6]

ご覧のとおり、最初の反復の終わりに、最後の要素を正しい場所に配置しました。今、私たちがする必要があるのは、同じ手順をさらに繰り返すことです。ただし、すでに並べ替えられている要素は除外します。

2番目の反復では、最後の要素を除く配列全体を反復処理します。同様に、3回目の反復では、最後の2つの要素を省略します。一般に、k回目の反復では、インデックス nk （除外）まで反復します。 n-1 の反復の最後に、ソートされた配列を取得します。

テクニックを理解したところで、実装について詳しく見ていきましょう。

3. 実装

Java8アプローチを使用して説明したサンプル配列の並べ替えを実装しましょう。

void bubbleSort(Integer[] arr) {
    int n = arr.length;
    IntStream.range(0, n - 1)
    .flatMap(i -> IntStream.range(1, n - i))
    .forEach(j -> {
        if (arr[j - 1] > arr[j]) {
            int temp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = temp;
            }
     });
}

そして、アルゴリズムの簡単なJUnitテスト：

@Test
public void whenSortedWithBubbleSort_thenGetSortedArray() {
    Integer[] array = { 2, 1, 4, 6, 3, 5 };
    Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 };
    BubbleSort bubbleSort = new BubbleSort();
    bubbleSort.bubbleSort(array);
    
    assertArrayEquals(array, sortedArray);
}

4. 複雑さと最適化

ご覧のとおり、平均および最悪の場合の、時間計算量は O（n ^ 2）です。

さらに、スペースの複雑さ、最悪のシナリオでも、はO（1）です。これは、バブルソートアルゴリズムが追加のメモリを必要とせず、ソートが元の配列で行われるためです。。

ソリューションを注意深く分析すると、反復でスワップが見つからない場合、さらに反復する必要がないことがわかります。

前に説明した例の場合、2回目の反復の後、次のようになります。

1 2 3 4 5 6

3回目の反復では、隣接する要素のペアを交換する必要はありません。したがって、残りのすべての反復をスキップできます。

ソートされた配列の場合、最初の反復自体ではスワッピングは必要ありません。つまり、実行を停止できます。これは最良のシナリオであり、アルゴリズムの時間計算量はO（n）です。

それでは、最適化されたソリューションを実装しましょう。

public void optimizedBubbleSort(Integer[] arr) {
    int i = 0, n = arr.length;
    boolean swapNeeded = true;
    while (i < n - 1 && swapNeeded) {
        swapNeeded = false;
        for (int j = 1; j < n - i; j++) {
            if (arr[j - 1] > arr[j]) {
                int temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
                swapNeeded = true;
            }
        }
        if(!swapNeeded) {
            break;
        }
        i++;
    }
}

最適化されたアルゴリズムの出力を確認してみましょう。

@Test
public void 
  givenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray() {
      Integer[] array = { 2, 1, 4, 6, 3, 5 };
      Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 };
      BubbleSort bubbleSort = new BubbleSort();
      bubbleSort.optimizedBubbleSort(array);
 
      assertArrayEquals(array, sortedArray);
}

5. 結論

このチュートリアルでは、バブルソートがどのように機能するか、およびJavaでの実装について説明しました。また、最適化する方法も確認しました。要約すると、これはインプレースの安定したアルゴリズムであり、時間計算量があります。

最悪の場合と平均的な場合：O（n * n）、配列が逆順の場合
最良の場合：O（n）、配列がすでにソートされている場合

このアルゴリズムは、並べ替えの小さなエラーを検出できるため、コンピュータグラフィックスで人気があります。たとえば、ほぼ並べ替えられた配列では、完全に並べ替えられた配列を取得するために、2つの要素のみを交換する必要があります。バブルソートはそのようなエラーを修正することができます（すなわち。この配列を線形時間で並べ替えます）。

いつものように、このアルゴリズムを実装するためのコードは、GitHubのにあります。

getdocs

13036