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

学生向けにプログラミングを無料で解説。Java、C++、Ruby、PHP、データベース、Ruby on Rails, Python, Django

Java | 10 | 並び替えプログラム

Java

ランキング参加中
プログラミング

<<前　 [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を指しています。


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


max =data[j];


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


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


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


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


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


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


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


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


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


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


[0][1][2][3][4][5][6][7][8][9][10][11][12][13][14]
データ１０７５２４３２９８７２８８４３６０３５５４６２２１２８２
一回目９８７５２４３２１０７２８８４３６０３５５４６２２１２８２
２回目９８８８２４３２１０７２７５４３６０３５５４６２２１２８２
３回目９８８８８２３２１０７２７５４３６０３５５４６２２１２２４
４回目９８８８８２７５１０７２３２４３６０３５５４６２２１２２４
５回目９８８８８２７５７２１０３２４３６０３５５４６２２１２２４
６回目９８８８８２７５７２６２３２４３６０３５５４１０２１２２４
７回目９８８８８２７５７２６２６０４３３２３５５４１０２１２２４
８回目９８８８８２７５７２６２６０５４３２３５４３１０２１２２４
９回目９８８８８２７５７２６２６０５４４３３５３２１０２１２２４
１０回目９８８８８２７５７２６２６０５４４３３５３２２４２１２１０
１１回目９８８８８２７５７２６２６０５４４３３５３２２４１２２１０
１２回目９８８８８２７５７２６２６０５４４３３５３２２４１２１０２


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


出力結果です。


Sort.java実行結果
Sort.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(小さい方の数字)を代入します。
この作業を一番左から順に（今回の場合は１０）最後まで行います。
最後までいったらまた最初のfor文まで戻りまた左から順にひっくり返していきます。


[0][1][2][3][4][5][6][7][8][9][10][11][12][13][14]
データ１０７５２４３２９８７２８８４３６０３５５４６２２１２８２
一回目７５２４３２９８７２８８４３６０３５５４６２１０１２８２２
２回目７５３２９８７２８８４３６０３５５４６２２４１２８２１０２
３回目７５９８７２８８４３６０３５５４６２３２２４８２１２１０２
４回目９８７５８８７２６０４３５４６２３５３２８２２４１２１０２
５回目９８８８７５７２６０５４６２４３３５８２３２２４１２１０２
６回目９８８８７５７２６０６２５４４３８２３５３２２４１２１０２
７回目９８８８７５７２６２６０５４８２４３３５３２２４１２１０２
８回目９８８８７５７２６２６０８２５４４３３５３２２４１２１０２
９回目９８８８７５７２６２８２６０５４４３３５３２２４１２１０２
１０回目９８８８７５７２８２６２６０５４４３３５３２２４１２１０２
１１回目９８８８７５８２７２６２６０５４４３３５３２２４１２１０２
１２回目９８８８８２７５７２６２６０５４４３３５３２２４１２１０２


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


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


出力結果です。


Sort2.java実行結果
Sort2.java実行結果


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

ランキング参加中
プログラミング


<<前　 [TOP] 　次>>

関連記事（外部サイト）