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のにあります。