Java | 12 | 並び替え - 学生向けプログラミング入門

↓↓クリックして頂けると励みになります。

Javaで数字の並び替えを行うにはArraysクラスのsortメソッドを使用する方法が一般的ですが、sortメソッドを使用しない並び替えプログラムを解説します。
まずは最も簡単な方法を紹介します。

Visual Studio Codeで以下の「Sort.java」ファイルを作成して下さい。

新規作成　【Sort.java】

public class Sort {
	public static void main( String[] args ) {

		int[] data = { 10, 75, 24, 32, 98, 72, 88, 43, 60, 35, 54, 62, 2, 12, 82, };

		for( int i=0; i<data.length-1; i++ ) {
			int max = data[i];
			int maxIndex = i;

			for( int j=i+1; j<data.length; j++ ) {
				if( data[j] > max ) {
					max = data[j];
					maxIndex = j;
				}
			}
			data[maxIndex] = data[i];
			data[i] = max;
		}
		for( int i=0; i<data.length; i++ ) {
			System.out.println( (i+1) + ":" + data[i] );
		}
	}
}

このプログラムでは二重ループを使って隣同士の数字の大きさを比べます。
数字が大きければその数字を最大値とおいてまた隣同士を比べます。

まず最初のfor文で次の様に記述しています。

int max = data[i];

ここで i は最初 0ですから、配列データのdata[0]=10を示しています。
max=10としているわけです。

そのまま次のfor文に入り、data[j]とmaxを比べていきます。
ここで j はj = i + 1なので、j = 1となりますから、配列データのdata[1]=75を指しています。

10と75を比べれば当然75の方が大きいのでif文の条件に当てはまり、次の処理が行われます。

max =data[j];

ここで今、 data[j] は75のことですから、max=75となりました。
そのままこのループは続き、75と24，75と32、75と98という感じで順番に大きさを比べていきます。
75と98を比べた時点でmaxは98となりました。
98より大きな数字はないので、max=98のままこの内側のループを抜けます。
ここで次の処理が行われます。

data[maxIndex] = data[i];
data[i] = max;

ここで、maxIndexは98のインデックスを指しますから、data[4] = 98よりMaxIndex=4となっているはずです。
代入して書き直すと次のようになります。

data[4] = data [0];
data[0] = 98;

この処理によりdata[4]にdata[0]の10が代入され、data[0]にはmaxの98が代入されました。

今の時点で配列は次のように変わりました。

int[] data = { 98, 75, 24, 32, 10, 72, 88, 43, 60, 35, 54, 62, 2, 12, 82, };

そしてまた最初のfor文に戻り、今度はi=1となるのでmaxは75で内側のループに入り隣と大きさを比べていく処理を繰り返します。

最初のfor文の i < data.length-1のところを i < data.length というようにしてもプログラムは動きますが、一つ無駄な処理が増えます。

最後もfor文で結果を出力しています。

	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]	[12]	[13]	[14]
データ	10	75	24	32	98	72	88	43	60	35	54	62	2	12	82
1回目	98	75	24	32	10	72	88	43	60	35	54	62	2	12	82
2回目	98	88	24	32	10	72	75	43	60	35	54	62	2	12	82
3回目	98	88	82	32	10	72	75	43	60	35	54	62	2	12	24
4回目	98	88	82	75	10	72	32	43	60	35	54	62	2	12	24
5回目	98	88	82	75	72	10	32	43	60	35	54	62	2	12	24
6回目	98	88	82	75	72	62	32	43	60	35	54	10	2	12	24
7回目	98	88	82	75	72	62	60	43	32	35	54	10	2	12	24
8回目	98	88	82	75	72	62	60	54	32	35	43	10	2	12	24
9回目	98	88	82	75	72	62	60	54	43	35	32	10	2	12	24
10回目	98	88	82	75	72	62	60	54	43	35	32	24	2	12	10
11回目	98	88	82	75	72	62	60	54	43	25	32	24	12	2	10
12回目	98	88	82	75	72	62	60	54	43	35	32	24	12	10	2

表ではは12回の繰り返しで並び替えが終わっていますが、実際は14回繰り返しています。
(data.length-1）回繰り返せばどんなパターンでも並べ替えが終わります。

コンパイルして実行結果を確認して下さい。

~/Desktop/Programming/JP $ javac Sort.java 

~/Desktop/Programming/JP $ java Sort      
1:98
2:88
3:82
4:75
5:72
6:62
7:60
8:54
9:43
10:35
11:32
12:24
13:12
14:10
15:2

Visual Studio Codeで以下の「Sort2.java」ファイルを作成して下さい。

新規作成　【Sort2.java】

public class Sort2 {
	public static void main( String[] args ) {

		int[] data = { 10, 75, 24, 32, 98, 72, 88, 43, 60, 35, 54, 62, 2, 12, 82, };

		int tmp=0;

		for( int i=0; i<data.length-1; i++ ) {

			for( int j=0; j<data.length-i-1; j++ ) {

				if( data[j] < data[j+1] ) {
					tmp = data[j];
					data[j] = data[j+1];
					data[j+1] = tmp;
				}
			}
		}

		for( int i=0; i<data.length; i++ ) {
			System.out.println( (i+1) + ":" + data[i] );
		}
	}
}

この並べ替えのプログラムは、隣同士の大きさを比べて大きかったらひっくり返すといった処理をひたすら繰り返し並び替えるといった手法をとっています。
バブルソートと呼ばれています。
「Sort.java」よりも少ない処理回数で並び替えることができます。

内側のループのif文を見てください。

もし右側の数字の方が大きかったらまずtmpという変数に小さい方の数字を代入しています。

次に小さい数字のあった場所に大きい方の数字を代入します。
最後に大きい方の数字があった場所にtmp(小さい方の数字)を代入します。
この作業を一番左から順に（今回の場合は10）最後まで行います。
最後までいったらまた最初のfor文まで戻りまた左から順にひっくり返していきます。

	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]	[12]	[13]	[14]
データ	10	75	24	32	98	72	88	43	60	35	54	62	2	12	82
1回目	75	24	32	98	72	88	43	60	35	54	62	10	12	82	2
2回目	75	32	98	72	88	43	60	35	54	62	24	12	82	10	2
3回目	75	98	72	88	43	60	35	54	62	32	24	82	12	10	2
4回目	98	75	88	72	60	43	54	62	35	32	82	24	12	10	2
5回目	98	88	75	72	60	54	62	43	35	82	32	24	12	10	2
6回目	98	88	75	72	60	62	54	43	82	35	32	24	12	10	2
7回目	98	88	75	72	62	60	54	82	43	35	32	24	12	10	2
8回目	98	88	75	72	62	60	82	54	43	35	32	24	12	10	2
9回目	98	88	75	72	62	82	60	54	43	35	32	24	12	10	2
10回目	98	88	75	72	82	62	60	54	43	35	32	24	12	10	2
11回目	98	88	75	82	72	62	60	54	43	35	32	24	12	10	2
12回目	98	88	82	75	72	62	60	54	43	35	32	24	12	10	2

表ではは12回の繰り返しで並び替えが終わっていますが、実際は14回繰り返しています。
（data.length-1）回繰り返せばどんなパターンでも並べ替えが終わります。

内側のfor文が(data.length-i-1)回しかループしていないので、その分「Sort.java」よりこちらの方が効率が良いと言えます。

Javaプログラム「Sort2.java」をコンパイルして出力結果を確認して下さい。

~/Desktop/Programming/JP $ javac Sort2.java

~/Desktop/Programming/JP $ java Sort2      
1:98
2:88
3:82
4:75
5:72
6:62
7:60
8:54
9:43
10:35
11:32
12:24
13:12
14:10
15:2