【Java】バブルソート

この記事は、「新・明解Javaで学ぶアルゴリズムとデータ構造」を読んで学んだことを、個人的な備忘録目的でまとめています。

ただし、本を参考にして自分なりに構成やコードを変更しているためご注意ください。
アルゴリズムの詳細や解説は是非参考書をお手に取って読まれてください。

【リンク紹介】
・Javaで学ぶアルゴリズムとデータ構造
・これまで書いたシリーズ記事一覧

バブルソート１

package chap06;

import java.util.Scanner;

//--- バブルソート（基本形） ---//
public class BubbleSort {
	
	//--- 配列の要素a[idx1]とa[idx2]の値を交換 ---//
	static void swap(int[] a, int idx1, int idx2) {
		int   t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}
	
	//--- バブルソート ---//
	static void bubbleSort(int[] a, int n) {
		
		// ソートのたびに操作する配列の幅を左から狭める
		for (int i = 0; i < n - 1; i++) {

			// 配列の右側から順番にソート
			for (int j = n - 1; j > i; j--) {
				
				if (a[j - 1] > a[j]) {
					// 配列の要素a[j - 1]とa[j]の値を交換
					swap(a, j - 1, j);
					
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		System.out.println("単純交換ソート（バブルソート）");
		System.out.print("要素数：");
		int nx  = stdIn.nextInt();
		int[] x = new int[nx];
		
		for (int i = 0; i < nx; i++) {
			System.out.print("x[" + i + "]：");
			x[i] = stdIn.nextInt();
		}
		
		bubbleSort(x, nx);    // 配列xをバブルソート
		
		System.out.println("昇順にソートしました。");
		
		for (int i = 0; i < nx; i++)
			System.out.println("x[" + i + "]=" + x[i]);
	}

}

バブルソート２

package chap06;

import java.util.Scanner;

//--- バブルソート（交換回数による打ち切り） ---//
public class BubbleSort2 {
	
	//--- 配列の要素a[idx1]とa[idx2]の値を交換 ---//
	static void swap(int[] a, int idx1, int idx2) {
		int   t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}
		
	//--- バブルソート ---//
	static void bubbleSort(int[] a, int n) {
						
		// ソートのたびに操作する配列の幅を左から狭める
		for (int i = 0; i < n - 1; i++) {

			// 交換回数
			int exchg = 0;

			// 配列の右側から順番にソート
			for (int j = n - 1; j > i; j--) {
					
				if (a[j - 1] > a[j]) {
						
					// 配列の要素a[j - 1]とa[j]の値を交換
					swap(a, j - 1, j);
					exchg++;
				}
			}
				
			// 交換が行われなかったら修了
			if (exchg == 0) break;
		}
	}
		
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		System.out.println("単純交換ソート（バブルソート）");
		System.out.print("要素数：");
		int nx  = stdIn.nextInt();
		int[] x = new int[nx];
			
		for (int i = 0; i < nx; i++) {
			System.out.print("x[" + i + "]：");
			x[i] = stdIn.nextInt();
		}
			
		bubbleSort(x, nx);    // 配列xをバブルソート
		
		System.out.println("昇順にソートしました。");
			
		for (int i = 0; i < nx; i++)
			System.out.println("x[" + i + "]=" + x[i]);
	}
}

バブルソート３

package chap06;

import java.util.Scanner;

//--- バブルソート（操作範囲を限定する） ---//
public class BubbleSort3 {
	
	//--- 配列の要素a[idx1]とa[idx2]の値を交換 ---//
	static void swap(int[] a, int idx1, int idx2) {
		int   t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}
		
	//--- バブルソート ---//
	static void bubbleSort(int[] a, int n) {
		
		// a[k]よりまえはソート済み
		int k = 0;
		
		while (k < n - 1) {
			
			int last = n - 1;
			
			// 配列の右側から順番にソート
			for (int j = n - 1; j > k; j--){
				
				if (a[j - 1] > a[j]) {
					
					// 配列の要素a[j - 1]とa[j]の値を交換
					swap(a, j - 1, j);
					last = j;
				}
			}
			
			// ソート後の一番最後の要素の位置lastをkに格納
			k = last;
		}
	}
		
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		System.out.println("単純交換ソート（バブルソート）");
		System.out.print("要素数：");
		int nx  = stdIn.nextInt();
		int[] x = new int[nx];
			
		for (int i = 0; i < nx; i++) {
			System.out.print("x[" + i + "]：");
			x[i] = stdIn.nextInt();
		}
			
		bubbleSort(x, nx);    // 配列xをバブルソート
		
		System.out.println("昇順にソートしました。");
			
		for (int i = 0; i < nx; i++)
			System.out.println("x[" + i + "]=" + x[i]);
	}
}

学習内容まとめ

eclipse操作時に役立つショートカットまとめ
https://qiita.com/toshi0383/items/1d2a990392998789062c

$\bf{\textcolor{red}{記事が役に立った方は「いいね」を押していただけると、すごく喜びます \ 笑}}$
ご協力のほどよろしくお願いします。