学生向けプログラミング入門

学生向けにプログラミングを解説。Java、C++、Ruby、PHP、データベース

Javaプログラミング入門その10 並び替えプログラム

<<前  [TOP]  次>>


並び替えには、いろいろな方法がありますが、まずは最も簡単な方法を紹介します。


メモ帳を開いて次のプログラムを作ってみましょう。


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]
データ1075243298728843603554621282
一回目9875243210728843603554621282
2回目9888243210727543603554621282
3回目9888823210727543603554621224
4回目9888827510723243603554621224
5回目9888827572103243603554621224
6回目9888827572623243603554101224
7回目9888827572626043323554101224
8回目9888827572626054323543101224
9回目9888827572626054433532101224
10回目9888827572626054433532241210
11回目9888827572626054433532241210
12回目9888827572626054433532241210


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


出力結果です。





メモ帳を開いて次のプログラムを作ってみましょう。


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]
データ1075243298728843603554621282
一回目7524329872884360355462101282
2回目7532987288436035546224128210
3回目7598728843603554623224821210
4回目9875887260435462353282241210
5回目9888757260546243358232241210
6回目9888757260625443823532241210
7回目9888757262605482433532241210
8回目9888757262608254433532241210
9回目9888757262826054433532241210
10回目9888757282626054433532241210
11回目9888758272626054433532241210
12回目9888827572626054433532241210


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


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


出力結果です。





<<前  [TOP]  次>>