Javaバブルソート：ガイド

Javaバブルソートの書き方

プログラマーがバブルの種類について話すとき、彼らはあなたがおそらくあなたの人生のある時点で吹き飛ばした水の泡について話していません。彼らは、アイテムのリストを並べ替えるために使用される並べ替えアルゴリズムについて話している。

このガイドでは、バブルの種類とその仕組みについて説明します。このアルゴリズムがどのようにコードに変換されるかを理解できるように、Javaを使用してバブルソートを実装します。さらに面倒なことはせずに、Javaバブルソートに飛び込みましょう！

Javaバブルソートとは何ですか？

バブルソートは、隣接する要素を比較し、それらが間違った順序で表示された場合にそれらを交換することによって値をソートするアルゴリズムです。

このプロセスは、リスト内のすべてのアイテムが正しく順序付けられるまで繰り返されます。バブルソートを使用して、リストを昇順または降順でソートできます。

バブルソートは、アルゴリズムクラスで教えられる最初のソートです。これは、挿入ソートや選択ソートなどの他のソートよりも理解しやすく、ソートアルゴリズムの優れた入門書となるためです。

バブルソートは、データがすでにほぼソートされている場合に最も効果的です。ただし、データがまったく並べ替えられていない場合は、別の種類の並べ替えの方が効率的です。

バブルソートはどのように機能しますか？

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

次のリストを検討してください。

参加者の81％は、ブートキャンプに参加した後、自分たちの技術的な仕事の見通しについてより自信を持っていると述べました。今日のブートキャンプにマッチしましょう。

平均的なブートキャンプの卒業生は、ブートキャンプの開始から最初の仕事を見つけるまで、キャリアの移行に6か月も費やしませんでした。

5

9

2

7

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

最初の要素が2番目の要素より大きい場合、これらの要素は位置を入れ替えます。この場合、5は9以下であるため、要素は同じ場所にとどまります。

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

5

2

9

7

このプロセスは、リスト内のすべてのアイテムが比較されるまで繰り返されます。この場合、実行する比較がもう1つあります。9は7より大きいですか？ 9は7より大きいため、これらの数値は入れ替わります。

5

2

7

9

私たちのリストはほぼ注文されています。すべてのアイテムが比較されると、すべての要素がソートされるまで、バブルソートが最初からやり直されます。

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

2

5

7

9

これで、リストが正しく順序付けられました。バブルソートは、リストの最後に到達するまで数値を比較し続け、その後停止します。バブルソートについてはこれですべてです。一度コツをつかめば、間違いなく簡単に使用できるアルゴリズムです。

Javaバブルソートの書き方

理論を知ることは1つのことですが、Javaバブルの種類について学ぶためにここに来ました。 Javaでバブルソートを実装する方法について最もよく説明します。

バブルの種類には2つのタイプがあります。

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

標準のバブルソートでは、配列がソートされている場合でも、可能なすべての比較が行われます。これにより、バブルソートの実行にかかる時間が長くなります。これにより、並べ替えの効率が低下します。

最適化されたバブルソートは、追加の変数を使用してリストがソートされているかどうかを追跡します。これにより、リストが並べ替えられるとすぐに並べ替えを停止できます。

標準的なバブルソートを書くことから始めましょう。

標準のバブルソート

まず、配列ライブラリをコードにインポートします。これをコードの後半で使用して、並べ替えられた数値のリストをコンソールに出力します。

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ループを初期化して、配列内の各アイテムを比較できるようにします。

リストの左側の項目が右側の数値よりも大きい場合、値が交換されます。そうでなければ、何も起こりません。

このスワップは、左側の値を「一時的」と呼ばれる変数に割り当てることによって実行されます。右側の値に、比較の左側にあった値を割り当てます。次に、左側の値に一時変数の値が割り当てられます。

6と5を比較する場合、それらは交換されます。したがって、リストは次のように表示されます：6、5。

私たちのプログラムはまだ何もしていません。関数を呼び出してソートするリストを提供するメインプログラムは作成していません。

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という変数を宣言しました。次に、sortingAlgorithmと呼ばれるBubbleSortクラスのインスタンスを宣言しました。これは、コードの次の行で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」という変数を宣言しました。この変数は、スワップが行われたかどうかを追跡します。デフォルトでは、この変数は「false」に設定されています。スワップが行われると、この変数の値は「true」に設定されます。

forループの最後に、hasSwappedがfalseに等しいかどうかを確認するifステートメントを追加しました。スワップが行われていない場合、配列はソートされます。 hasSwappedがfalseに等しい場合、「break」キーワードを使用してループの実行を停止します。

以前に作成したメインプログラムを使用してコードを実行し、何が起こるかを見てみましょう。

[2, 5, 7, 9]

リストは並べ替えられていますが、今回はアルゴリズムの方が効率的です。より多くの値を含むより大きなリストを使用してソートすると、このアルゴリズムの優れたパフォーマンスがより明確になります。これで、Javaで最適化されたバブルソートを作成できました！

結論

バブルソートは、リストを昇順または降順でソートするために使用されます。それらは隣接する値を比較し、それらが間違った順序である場合はそれらを交換することによって機能します。

バブルソートには、標準と最適化の2種類があります。標準のバブルソートは事前定義された数のスワップを実行しますが、最適化されたバブルソートは、リストがソートされるまでソートを継続します。

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