バブルソート bubble sort

2020-09-02

こんにちは、0371です。

今回は、配列を二分割していきながら、任意の値が格納されている添字を導き出す方法について書いていきます。
基本情報技術者試験のアルゴリズムの問題集から、擬似言語の問題を実際の言語でプログラミングしてみました。

バブルソートとは？

配列の端からもう一方の端に向かって隣同士を比較し、配列の先頭からソートの範囲を狭めつつ、小さい値が前になるように値を交換することを繰り返すソートです。

コード

今回も、ArrayListを使用して、ランダムな配列を生成し、昇順にソートしていきます。言語はJavaです。

任意の値が見つかったら探索を終了するプログラム

Main.java

import java.util.ArrayList;
import java.util.Random;

public class Main {

	public static void main(String[] args) {
		int listsize = 5;
		int range = 10;

		ArrayList<Integer> list = new ArrayList<>();
		Random rand = new Random();
		for(int i=0; i<listsize; i++)list.add(rand.nextInt(range));
		System.out.println("整列前の配列: "+list);
		System.out.println();
		bubbleSort(list);
		System.out.println();
		System.out.println("整列後の配列: "+list);
	}

	private static void bubbleSort(ArrayList<Integer> list) {
		int count = 0;
		for (int lis_i = 0; lis_i < list.size(); lis_i++) {

			count++;
			System.out.println();
			System.out.println("------");
			System.out.println(count+"回目のループ");
			System.out.println();
			System.out.println(list);

			for (int pos = list.size()-1; pos > lis_i; pos--) {
				System.out.println("配列の["+pos+"]番目と["+(pos-1)+"]番目を比較しています。");

				if(list.get(pos) < list.get(pos-1)) {
					System.out.println();
					System.out.println(list.get(pos)+"が"+list.get(pos-1)+"よりも小さいため、値の交換を行います。");

					int temp = list.get(pos);

					list.set(pos, list.get(pos-1));
					System.out.println("["+pos+"]: "+list.get(pos));

					list.set(pos-1, temp);
					System.out.println("["+(pos-1)+"]: "+list.get(pos-1));

					System.out.println();
					System.out.println("整列中の配列: "+list);

				} else {
					System.out.println("値の交換はしませんでした。");
				}
			}
		}
	}
}

確認なしverはこちら

import java.util.ArrayList;
import java.util.Random;

public class Main {

	public static void main(String[] args) {
		int listsize = 5;
		int range = 10;

		ArrayList<Integer> list = new ArrayList<>();
		Random rand = new Random();
		for(int i=0; i<listsize; i++)list.add(rand.nextInt(range));

		bubbleSort(list);
		System.out.println(list);
	}

	private static void bubbleSort(ArrayList<Integer> list) {
		for (int lis_i = 0; lis_i < list.size(); lis_i++) {
			for (int pos = list.size()-1; pos > lis_i; pos--) {
				if(list.get(pos) < list.get(pos-1)) {
					int temp = list.get(pos);
					list.set(pos, list.get(pos-1));
					list.set(pos-1, temp);
				}
			}
		}
	}
}

Random()とnextInt();を使用することによって、実行するたびに1~10までのランダムなint型の数値を配列の中身へ代入しています。

bubbleSort()の二重ループのif文の中では、値の交換を行っています。

一時的に値を退避させておく変数tempを用意し、その中に大きい値を代入します。
大きい値が入っていた添字に、小さい値を代入します。
小さい値が入っていた添字に、大きい値を代入します。

確認ありverで、何度か実行した結果は以下の通りです。

整列前の配列: [5, 3, 8, 4, 9]


------
1回目のループ

[5, 3, 8, 4, 9]
配列の[4]番目と[3]番目を比較しています。
値の交換はしませんでした。
配列の[3]番目と[2]番目を比較しています。

4が8よりも小さいため、値の交換を行います。
[3]: 8
[2]: 4

整列中の配列: [5, 3, 4, 8, 9]
配列の[2]番目と[1]番目を比較しています。
値の交換はしませんでした。
配列の[1]番目と[0]番目を比較しています。

3が5よりも小さいため、値の交換を行います。
[1]: 5
[0]: 3

整列中の配列: [3, 5, 4, 8, 9]

------
2回目のループ

[3, 5, 4, 8, 9]
配列の[4]番目と[3]番目を比較しています。
値の交換はしませんでした。
配列の[3]番目と[2]番目を比較しています。
値の交換はしませんでした。
配列の[2]番目と[1]番目を比較しています。

4が5よりも小さいため、値の交換を行います。
[2]: 5
[1]: 4

整列中の配列: [3, 4, 5, 8, 9]

------
3回目のループ

[3, 4, 5, 8, 9]
配列の[4]番目と[3]番目を比較しています。
値の交換はしませんでした。
配列の[3]番目と[2]番目を比較しています。
値の交換はしませんでした。

------
4回目のループ

[3, 4, 5, 8, 9]
配列の[4]番目と[3]番目を比較しています。
値の交換はしませんでした。

------
5回目のループ

[3, 4, 5, 8, 9]

整列後の配列: [3, 4, 5, 8, 9]

整列前の配列: [5, 9, 5, 6, 9]


------
1回目のループ

[5, 9, 5, 6, 9]
配列の[4]番目と[3]番目を比較しています。
値の交換はしませんでした。
配列の[3]番目と[2]番目を比較しています。
値の交換はしませんでした。
配列の[2]番目と[1]番目を比較しています。

5が9よりも小さいため、値の交換を行います。
[2]: 9
[1]: 5

整列中の配列: [5, 5, 9, 6, 9]
配列の[1]番目と[0]番目を比較しています。
値の交換はしませんでした。

------
2回目のループ

[5, 5, 9, 6, 9]
配列の[4]番目と[3]番目を比較しています。
値の交換はしませんでした。
配列の[3]番目と[2]番目を比較しています。

6が9よりも小さいため、値の交換を行います。
[3]: 9
[2]: 6

整列中の配列: [5, 5, 6, 9, 9]
配列の[2]番目と[1]番目を比較しています。
値の交換はしませんでした。

------
3回目のループ

[5, 5, 6, 9, 9]
配列の[4]番目と[3]番目を比較しています。
値の交換はしませんでした。
配列の[3]番目と[2]番目を比較しています。
値の交換はしませんでした。

------
4回目のループ

[5, 5, 6, 9, 9]
配列の[4]番目と[3]番目を比較しています。
値の交換はしませんでした。

------
5回目のループ

[5, 5, 6, 9, 9]

整列後の配列: [5, 5, 6, 9, 9]

成功していますね。

今日の一言

バブルソートは初歩的な知識。値の交換のテクニックは必須で覚えよう。

バブルソート bubble sort

バブルソート とは？

コード

任意の値が見つかったら探索を終了するプログラム

今日の一言

バブルソートとは？