バブルソートについて話す

バブルソート入門

バブルソートは、そのシンプルさと実装のしやすさ、そして原理のわかりやすさから、最もポピュラーなソート方法のひとつです。バブリングソートという名前が示すように、その並べ替えプロセスは水の中の泡のように、1つずつ表面に上がってきます。

バブルソート・コードの実装

import java.util.Arrays;
public class MaopaoSort {
	
	static int[] array = {3,2,4,1,5,0};
	
	public static void maopaoSort(int[] a) 
	{
		//外側のループは、比較のラウンド数は、5回の合計を実施することができる
		for(int i=0;i<a.length-1;i++) 
		{
			//メモリループは、各ラウンドで実行される2対2の比較である
			for(int j=0;j<a.length-1;j++) 
			{
				if(a[j] > a[j+1]) 
				{
					int temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp; 
				}
			}
			System.out.println(" "+(i+1)+"ソートのラウンドの後、配列は: "+Arrays.toString(a));
		}
	}
	
	public static void main(String[] args) {
		maopaoSort(array);
	}
}

バブリングソートの最適化

1 .上記のコードと実行結果を観察すると、最初のラウンドが終わったとき、最後の数字は配列の中で最大の要素でなければならないことがわかります。そうすると、コードは次のように修正できます：

public static void maopaoSort(int[] a) 
{
	//外側のループは、比較のラウンド数は、5回の合計を実施することができる
	for(int i=0;i<a.length-1;i++) 
	{
		//メモリループは、各ラウンドで実行される2対2の比較である
 //そして、各ラウンドの終了後、次の2つの2つの比較は、1つ未満の比較することができる
		for(int j=0;j<a.length-i-1;j++) 
		{
			if(a[j] > a[j+1]) 
			{
				int temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp; 
			}
		}
		System.out.println(" "+(i+1)+"ソートのラウンドの後、配列は: "+Arrays.toString(a));
	}
}

これは、ここで考えることができる、2つの比較のラウンドは、配列の要素のどれもスワップしない場合は、実際にはソート作業が完了しているので、プロシージャ内のフラグを追加することを検討することができます、デフォルトでは、要素のスワップかどうかの比較のラウンドを意味し、falseです、プロシージャが要素のスワップに実行されると、フラグがtrueに設定され、比較のラウンドの最後に、もしフラグが真の場合、それは比較のラウンドは、要素のスワップで発生しなかったことを意味し、ソートが完了すると、フラグが真の場合、それは比較のこのラウンドはまだ要素のスワップであることを意味し、あなたはソートの次のラウンドに続行する必要があります。コードの実装は次のとおりです：

import java.util.Arrays;
public class MaopaoSort {
	
	static int[] array = {1,2,0,3,5,4};
	
	public static void maopaoSort(int[] a) 
	{
		//外側のループは、比較のラウンド数は、5回の合計を実施することができる
		for(int i=0;i<a.length-1;i++) 
		{
			boolean flag = false;
			//メモリループは、各ラウンドで実行される2対2の比較である
			for(int j=0;j<a.length-i-1;j++) 
			{
				if(a[j] > a[j+1]) 
				{
					int temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
					flag = true;
				}
			}
			System.out.println(" "+(i+1)+"ソートのラウンドの後、配列は: "+Arrays.toString(a));
			if(flag == false)
			{
				System.out.println("2つの比較のこのラウンドは、要素のスワップで発生しなかった、ソートが完了している！");
				return;
			}
		}
	}
	
	public static void main(String[] args) {
		maopaoSort(array);
	}
}