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回目の繰り返しでは、インデックス

n-k

までを繰り返します(除外)。

__n-1回の繰り返しが終わると、ソートされた配列が得られます。

テクニックを理解したので、実装に飛び込みましょう。


3実装

Java 8のアプローチを使用して説明したサンプル配列のソートを実装しましょう。

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)

です。

さらに、

スペースの複雑さ

は、たとえ最悪のシナリオであっても、Bubbleソートアルゴリズムは余分なメモリを必要としないので** は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結論

このチュートリアルでは、Bubble Sortがどのように機能するのか、またJavaでの実装について説明しました。また、最適化方法についても説明しました。まとめると、これは時間の複雑さを伴うインプレース安定アルゴリズムです。

  • 最悪および平均の場合:O(n ** n)、配列が逆の順序のとき

  • ベストケース:配列がすでにソートされている場合はO(n)

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

いつものように、このアルゴリズムの実装のためのコードはhttps://github.com/eugenp/tutorials/tree/master/algorithms-sorting[GitHubに乗って]を見つけることができます。