Javaのバブルソート徹底解説：基本から最適化まで

Javaバブルソートの書き方

プログラマーの間で「バブルソート」という言葉が出てくるとき、それは人生で一度は吹いたことがある水の泡のことではありません。バブルソートとは、リスト内の項目を順序付けるために使われるソート（整列）アルゴリズムのことを指します。

このガイドでは、バブルソートとは何か、そしてどのように動作するのかを解説します。さらにJavaでバブルソートを実装し、このアルゴリズムがどのようにコードに変換されるのかを理解できるようにします。それでは早速、Javaのバブルソートの世界へ飛び込みましょう！

Javaのバブルソートとは？

バブルソートとは、隣り合う要素同士を比較し、順序が正しくない場合にそれらを入れ替えることで値を並べ替えるアルゴリズムです。

この処理は、リスト内のすべての項目が正しく並ぶまで繰り返されます。バブルソートは、リストを昇順にも降順にも並べ替えることができます。

バブルソートは、アルゴリズムの授業で最初に学ぶソートです。挿入ソートや選択ソートなどの他のソートよりも理解しやすく、ソートアルゴリズムへの良い入門となるためです。

バブルソートは、データがすでにほぼ整列している場合に最も効果を発揮します。しかし、データがまったく整列されていない場合は、別の種類のソートの方が効率的かもしれません。

バブルソートの仕組み

Javaでバブルソートのコードを書き始める前に、まずこのアルゴリズムが実際にどのように実装されるのかを理解しておきましょう。

次のリストを考えてみます。

5

9

2

7

バブルソートは、リストの最初の要素と2番目の要素を比較することから始まります。

最初の要素が2番目の要素より大きい場合、これらの要素は位置を入れ替えます。この場合、5は9より大きくないため、要素は元の場所に留まります。

次に、リスト内の次の2つの項目を比較します。9は2より大きいので、これらの数値は入れ替わります。

5

2

9

7

このプロセスは、リスト内のすべての項目が比較されるまで繰り返されます。この場合、あと1回比較が必要です。9は7より大きいか？ 9は7より大きいので、これらの数値は入れ替わります。

5

2

7

9

リストはほぼ整列されました。すべての項目の比較が完了すると、バブルソートはすべての要素が整列するまで最初からやり直します。

5は2より大きいので、これらの数値は入れ替わります。

2

5

7

9

これでリストは正しく整列されました。バブルソートはリストの末尾に達するまで数値の比較を続け、その後停止します。これがバブルソートのすべてです。コツをつかめば、間違いなく簡単に使えるアルゴリズムです。

Javaでバブルソートを書く方法

理論を知ることも大切ですが、ここに来た目的はJavaのバブルソートについて学ぶことのはずです。では、Javaでバブルソートを実装する方法を見ていきましょう。

バブルソートには2種類あります。

• 標準的なバブルソート
• 最適化されたバブルソート

標準的なバブルソートは、配列がすでに整列されていても、可能な限りすべての比較を行います。そのため、実行にかかる時間が増加し、効率が低下します。

一方、最適化されたバブルソートは、追加の変数を使用してリストが整列済みかどうかを追跡します。これにより、リストが整列した時点でソートを停止できます。

まずは、標準的なバブルソートから書いてみましょう。

標準的なバブルソート

まず、Arraysライブラリをコードにインポートします。これは後ほど、整列された数値のリストをコンソールに出力するために使用します。

import java.util.Arrays;

これが済んだら、アルゴリズムの作成を始めましょう。

まず、Javaプログラムのコードを格納するBubbleSortというクラスと、ソートを実行する関数を定義します。

class BubbleSort {
	void sortNumbers(int array[]) {
		int size = array.length;

		for (int item = 0; item < size - 1; item++) {
			for (int j = 0; j < size - item - 1; j++) {
				if (array[j] > array[j + 1]) {
					int temporary = array[j];
					array[j] = array[j + 1];
					array[j + 1] = temporary;
				}
			}
		}
	}
}

ここでは、配列をパラメータとして受け取るsortNumbersという関数を宣言しています。この関数は、指定された数値リストのサイズを計算することから始まります。

サイズが計算されると、forループが初期化されます。このループは配列内のすべての項目を走査します。さらに内側のforループにより、配列内の各項目を隣接する項目と比較できるようになります。

左側の項目が右側の数値より大きい場合、値が入れ替えられます。そうでなければ、何も起こりません。

この入れ替えは、左側の値を「temporary」という変数に退避させることで行います。次に、右側の値を左側に代入し、最後に一時変数の値を右側に代入します。

例えば6と5が比較された場合、それらは入れ替えられ、リスト上では「5, 6」の順に並びます。

現時点では、プログラムはまだ何も行いません。関数を呼び出してソート対象のリストを渡すmainプログラムをまだ書いていないからです。

コード内のsortNumbers関数の下に、以下のコードを追加してください。

public static void main(String args[]) {
	int[] toSort = { 5, 9, 2, 7 };
	BubbleSort sortingAlgorithm = new BubbleSort();
	sortingAlgorithm.sortNumbers(toSort);
	System.out.println(Arrays.toString(toSort));
}

ここでは、ソートしたい値のリストを格納するtoSortという変数を宣言しています。次に、BubbleSortクラスのインスタンスsortingAlgorithmを作成し、その次の行でsortNumbers関数を呼び出します。この関数が呼び出されると、リストがソートされます。

最後に、Arrays.toString()メソッドを使用してリストを文字列に変換し、コンソールに出力できるようにします。コードの実行結果は以下の通りです。

[2, 5, 7, 9]

これで整列された配列が完成しました！

最適化されたバブルソート

コードをより効率的にする方法があります。現在の実装では、可能な限りすべての比較が完了するまでソートが続きます。つまり、配列がすでに整列されていても、すべての比較が終わるまで処理が止まりません。

この動作は、新しい変数をコードに追加することで防ぐことができます。これにより、リストが整列された時点でソートを早期に終了できます。先ほどのsortNumbers関数にこの変数を追加してみましょう。

class BubbleSort {
	void sortNumbers(int array[]) {
		int size = array.length;

		for (int item = 0; item < size - 1; item++) {
			boolean hasSwapped = false;
			for (int j = 0; j < size - item - 1; j++) {
				if (array[j] > array[j + 1]) {
					int temporary = array[j];
					array[j] = array[j + 1];
					array[j + 1] = temporary;

					hasSwapped = true;
				}
			}

			if (hasSwapped == false) {
				break;
			}
		}
	}
}

コードに3つの変更を加えました。まず、外側のforループの中でhasSwappedというboolean型の変数を宣言しました。この変数は、入れ替えが行われたかどうかを追跡します。デフォルトでは「false」に設定されており、入れ替えが発生すると「true」に更新されます。

次に、内側のforループの後に、hasSwappedがfalseかどうかをチェックするif文を追加しました。一周の間に一度も入れ替えが行われていない場合、配列はすでに整列されています。その際は「break」キーワードを使用してループの実行を停止します。

先ほど書いたmainプログラムを使ってコードを実行し、結果を確認してみましょう。

[2, 5, 7, 9]

リストは正しく整列されましたが、今回はアルゴリズムがより効率的になっています。より多くの値を持つ大きなリストをソートする場合、この最適化の効果はさらに顕著に表れるでしょう。これで、Javaで最適化されたバブルソートを書くことができました！

まとめ

バブルソートは、リストを昇順または降順に並べ替えるために使用されるアルゴリズムです。隣り合う値を比較し、順序が正しくない場合にそれらを入れ替えることで動作します。

バブルソートには、標準型と最適化型の2種類があります。標準的なバブルソートは決められた回数の比較をすべて行うのに対し、最適化されたバブルソートはリストが整列した時点で処理を終了できます。

これで、あなたもエキスパートのようにJavaでバブルソートを書き始める準備が整いました！