大きさの順に並べ替える

選択ソート

与えられた複数の数値のを大きさの順に並べる処理を考えます。最大値のデータを次々にとりだしていけば,できそうだと思いませんか。

プログラム名 OokiiJun01.java

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を探します。

プログラム名 OokiiJun02.java

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

課題

0.

人手による並べ替え

52, 46, 35, 56, 63, 98, 90, 45, 64, 82

1.

小さい順に並べるプログラムにしなさい。

最小値を左に集める方法と,最大値を右に集める方法がある。

プログラム名 ChiisaiJun01.java

もくじ

Javaプログラミング
聖愛中学高等学校
http://www.seiai.ed.jp/
Dec.2003
Dec.2008
Dec.2011