与えられた複数の数値のを大きさの順に並べる処理を考えます。最大値のデータを次々にとりだしていけば,できそうだと思いませんか。
public class OokiiJun01 { public static void main( String[] args ) { int[] data = { 52, 46, 24, 12, 15, 35, 18, 56, 63, 23, 10, 98, 29, 32, 90, 45, 64, 8, 16, 82 }; int[] ooki = new int[data.length]; //結果を入れる配列 for( int jn = 0; jn<data.length; jn++ ){ int max = data[0]; int sonoi = 0; //← for( int i=1; i<data.length; i++ ) { if( data[i] > max ){ max = data[i]; sonoi = i; //← } } ooki[ ■1 ] = max; data[sonoi] = ■2; //← } for (int i = 0; i < ooki.length; i++) { System.out.print(ooki[i] + " "); } System.out.println(); } }
動作結果
$ java OokiiJun01 98 90 82 64 63 56 52 46 45 35 32 29 24 23 18 16 15 12 10 8
jnによるforの内容はSaidai01.javaとほとんど同じです。これをデータ数分繰り返して最大なものをひろっています。ただ繰り返すだけだと毎回おなじ数値をひろいますから,一度ひろった数値をひろわないようにするのが//←印の部分です。いわば「済」マークをつけているわけです
data 52, 46, 24, 12, 15, 35, 18, 56, 63, 23, 10, 98, 29, 32, 90, 45, 64, 8, 16, 82
↓
ooki 98, 90, 82,
でも,普通はこうしません。プログラムとして済みマークの部分がわかりやすいとは言えません。最大の問題は,data[]とooki[]と2つの配列を使うのでデータ量が多いときはコンピュータのメモリを2倍使用してしまうことです。コンピュータの扱えるデータ量の限界に近くなるとこれは切実です。
配列をひとつだけにします。最大のものを左に寄せて,次からはそこより右側からmaxを探します。
public class OokiiJun02 { public static void main( String[] args ) { int[] data = { 52, 46, 24, 12, 15, 35, 18, 56, 63, 23, 10, 98, 29, 32, 90, 45, 64, 8, 16, 82 }; //int[] ooki = new int[data.length]; 結果を入れる配列を排除 for( int jn = 0; jn<data.length-1; jn++ ){ int max = data[jn]; int sonoi = jn; for( int i=jn+1; i<data.length; i++ ) { if( data[i] > max ){ max = data[i]; sonoi = i; } } data[sonoi] = data[jn]; data[jn] = max; } for (int i = 0; i < data.length; i++) { System.out.print(data[i] + " "); } System.out.println(); } }
これが標準的な最大値選択方式の並べ替えで選択ソートとよばれる種類の典型的な例です。
「範囲の中で最大なものを選択して範囲の一番端のものと交換し,範囲を狭める」ということを繰り返しています。
元データ
52, 46, 24, 12, 15, 35, 18, 56, 63, 23, 10, 98, 29, 32, 90, 45, 64, 8, 16, 82
4つ目を選択中
jn sonoi | | 98, 90, 82, 12, 15, 35, 18, 56, 63, 23, 10, 52. 29, 32, 46. 45, 64, 8, 16, 24
最後が jn<data.length-1 でいい理由
jn sonoi | | 98, 90, 82, 64, 63, 56, 52, 46, 45, 35, 32, 29, 24, 23, 18, 16, 15, 12, 8, 10
人手による並べ替え
52, 46, 35, 56, 63, 98, 90, 45, 64, 82
小さい順に並べるプログラムにしなさい。
最小値を左に集める方法と,最大値を右に集める方法がある。