Javaのバブルソート

バブル ソートは、Java でデータをソートするために最も一般的に使用されるアルゴリズムの 1 つです。並べ替えは、隣接する数値を再帰的に比較し、昇順または降順に移動して行われます。この要素のシフトは、すべての桁が必要な順序で完全にソートされるまで行われます。バブル ソートという名前は、配列バブルの要素が開始点となるためです。例を挙げてバブル ソート アルゴリズムを理解しましょう。

例: 昇順に並べる必要がある数値の配列 [6 1 8 5 3] を考えてみましょう。

無料ソフトウェア開発コースを始めましょう

Web 開発、プログラミング言語、ソフトウェア テスト、その他

バブル ソート アルゴリズムは、すべての数値が並べ替えられたことが判明するまで複数回反復して動作します。

反復

以下は、Java のバブル ソートで実行される反復です。

最初の反復

[6 1 8 5 3] – 最初の 2 つの数値を比較することから始まり、2 つの数値のうち小さい方の数値を右にシフトします。したがって、6 と 1 のうち、1 は左にシフトされ、6 は右にシフトされた小さい方の数になります。 [1 6 8 5 3] – 次に、位置を 1 つ右にシフトして、隣接する 2 つの数値を比較します。ここで、数値 6 は 8 より小さいため、同じ順序が維持されます。 [1 6 8 5 3] – 繰り返しますが、位置を 1 つ右にシフトすると、8 と 5 の間で比較が行われます。数値 5 は小さいほど左にシフトされます。 8.より [1 6 5 8 3] – ここでは、数値 8 と 3 の間で比較が行われます。数値 3 は 8 より小さいため、左にシフトされます。 [1 6 5 3 8] – これは、最初の反復後の注文の最終結果です。

2 回目の反復

数値がまだ完全に増加していないため、プログラムは 2 回目の反復に進みます。

[1 6 5 3 8] – ここでは、最初の反復結果の最初の 2 桁から再び比較が開始されます。数値 1 と 6 を比較し、1 は 6 より小さいため同じ順序を維持します。 [1 6 5 3 8] – ここでは、数字 5 と 6 が比較されます。必要な昇順に既に設定されているため、同じ順序が保持されます。 [1 5 6 3 8] – 数値 6 と 3 の間で比較が行われます。数値 3 は 6 より小さいため左にシフトされます。 [1 5 3 6 8] – 次に、数字 6 と 8 を比較します。同じ順序は、予想される順序のまま保持されます。 [1 5 3 6 8] – これは 2 回目の反復後の最終結果です。それでも、数字が昇順に完全に配置されていないことに気づくことができます。それでも、最終結果を得るには、5 番と 3 番を交換する必要があります。したがって、プログラムは 3 回目の反復に進みます。

3 回目の反復

[1 5 3 6 8] – 3 回目の反復は、最初の 2 桁、1 と 5 を比較することから始まります。順序は予想どおりであるため、同じままです。 [1 5 3 6 8]- 次に、隣接する数字 3 と 5 を比較します。 5は3より大きいので右側に移動します。 [1 3 5 6 8] – 反復は数値 5 と 6、6 と 8 を比較します。必要な順序になっているため、順序が保持されます。 [1 3 5 6 8] – 最後に、プログラムが隣接する各要素を比較し、すべての桁が昇順であることを確認すると、反復が停止します。

並べ替える必要があるのは配列の 5 つの要素だけなので、反復は 3 回だけかかりました。配列内の要素が増加すると、反復の量も増加します。

Java を使用したバブル ソートの実装

以下は、バブル ソート アルゴリズムを実装する Java コードです。 (Java の配列の最初の位置は 0 から始まり、1 ずつ増分して続きます。つまり、array[0]、array[1]、array[2] と続きます。)

コード:

import java.util.Scanner;
public class BubbleSort {
static void bubbleSort(int[] arraytest) {
int n = arraytest.length; //length of the array is initialized to the integer n
int temp = 0; //A temporary variable called temp is declared as an integer and initialized to 0
for(int i=0; i < n; i++){ // first for loop performs multiple iterations
for(int j=1; j < (n-i); j++){
if(arraytest[j-1] > arraytest[j]){ // if loop compares the adjacent numbers
// swaps the numbers
temp = arraytest[j-1]; // assigns the greater number to temp variable
arraytest[j-1] = arraytest[j]; // shifts the lesser number to the previous position
arraytest[j] = temp; // bigger number is then assigned to the right hand side
}
}
}
}
public static void main(String[] args) {
int arraytest[] ={23,16,3,42,75,536,61}; // defining the values of array
System.out.println("Array Before Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++){ // for loop used to print the values of array
System.out.print(arraytest[i] + " ");
}
System.out.println();
bubbleSort(arraytest); // array elements are sorted using bubble sort function
System.out.println("Array After Doing Bubble Sort");
for(int i=0; i < arraytest.length; i++){
System.out.print(arraytest[i] + " "); // for loop to print output values from array
}
}
}

出力:

Java におけるバブル ソートの長所と短所

Java のバブル ソートのさまざまな利点と欠点を以下に示します。

メリット

1. コードは非常に書きやすく、理解しやすいです。通常は数分しかかかりません。
2. 実装も非常に簡単です。
3. バブルソートは数値を並べ替えてメモリ内に保持するため、メモリを大幅に節約します。

デメリット

1. このアルゴリズムは、比較に時間がかかるため、大規模なデータセットには適していません。入力数値の並べ替えにかかる時間は急激に増加します。
2. O(n^2) はバブル ソートの平均複雑度、O(n) は最良の場合の複雑さ (最良の場合は要素が最初にソートされるとき) です。ここで、n は要素の数です。

リアルタイム アプリケーション

バブルソートは、ソート時の微小なエラーを検出できるため、コンピュータグラフィックスなどで利用されています。これは、ポリゴンの頂点の裏地を並べ替える必要があるポリゴン充填アルゴリズムでも使用されます。

結論

この記事では、バブル ソート アルゴリズムがどのように機能するのか、また Java プログラミングを使用して実装する方法について説明しました。バブル ソートは、比較的小さなデータセットに対して簡単に実装できる、非常に安定したアルゴリズムです。これは比較アルゴリズムの例であり、その単純さのため初心者によって使用されます。

以上がJavaのバブルソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。