ファイルから読み込む場合の並べ替え

状況にあった作戦

配列に入っているデータをソートするプログラムはできているので,ファイルから配列に読み込む部分を作って組み合わせれば,うまくいくのはわかります。このようにすでにあるものを組み合わせることでプログラム作成の手間を省くことができます。

javaはうまく使えばこの再利用がしやすいようにできています。

しかし読み込んでしまってから並べ替えるよりも一つ読んだら大きさを比べてちょうどよいところに挟み込めば手間が省けそうです。このようなソートを挿入ソートといいます。

ただデータ量が極端に多い場合はまた考え直さなければなりません。挿入ソートはそれほど速いソートでないからです。

配列を作るところだけ交換

この方法はソートの方法とは無関係です。選択ソートでもバブルソートでも使えます

プログラム名 OokiiJun21.java

最も簡単なやり方です。

        int[] data = { 52, 46, 24, 12, 15,
                       35, 18, 56, 63, 23,
                       10, 98, 29, 32, 90,
                       45, 64,  8, 16, 82
                     };

の部分をたとえば次のように変えます

        int[] data = new int[20];
        int ct  = 0;
        String fname = "data01.txt";
        try {
            FileReader   in  = new FileReader(fname);
            BufferedReader inb = new BufferedReader(in);
            String line;
            while ((line = inb.readLine()) != null) {
                data[ct] = Integer.parseInt(line);
                ct++;
            }
            inb.close();
            in.close();
        }
        catch (IOException e) {
            System.err.println( fname + " がないのでは?" );
            System.err.println( e);
        }

ただし次をお忘れなく

import java.io.*;

配列を使う場合はデータ数を合わせる方法に気を遣います。今回はあらかじめわかっている数で配列を作りました。データの最初にデータ数を書く方法(これは簡単だが危険)。配列を多めに用意して読み込んだデータの数だけ使う方法などがあります。

挿入ソート

たとえば,次のように並んでいるところに,18を挿入します。

24 15 12

次の位置になりますが,配列の場合はずらして場所を空ける作業が必要です。

24   15 12

今回は小さい方から比較して1つずつずらすことにします。

1.18と12を比較

    18  
24 15 12  

18が大きいので12をずらす

    18  
24 15   12

15と18を比較

  18    
24 15   12

18が大きいので12をずらす

  18    
24   15 12

24と18を比較

18      
24   15 12

24が大きいので18を一つ前に入れる

     
24 18 15 12

プログラム名 OokiiJun22.java

import java.io.*;

public class OokiiJun22 {
    public static void main( String[] args ) {
        int[] data = new int[20];
        int lastindex =0;
        String fname = "data01.txt";
        try {
            FileReader   in  = new FileReader(fname);
            BufferedReader inb = new BufferedReader(in);
            String line;
            line = inb.readLine();
            data[0] = Integer.parseInt(line);
            lastindex=0;
            while ((line = inb.readLine()) != null) {
                int x = Integer.parseInt(line);
                int i= lastindex;
                while ( i >= 0 && x >= data[i]  ) {
                    data[■] = data[■];
                    i--;
                }
                data[i+1] = x;
                lastindex++;
            }
            inb.close();
            in.close();
        }
        catch (IOException e) {
            System.err.println( fname + " がないのでは?" );
            System.err.println( e);
        }
        for (int i = 0; i <= Math.min(lastindex, 25 ) ; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }
}

動作結果

結果は同じですが、こうなるかは■の内容によります。

$ java OokiiJun22
98 90 82 64 63 56 52 46 45 35 32 29 24 23 18 16 15 12 10 8

途中経過

52
52 46
52 46 24
52 46 24 12
52 46 24 15 12
52 46 35 24 15 12
52 46 35 24 18 15 12
56 52 46 35 24 18 15 12
63 56 52 46 35 24 18 15 12
63 56 52 46 35 24 23 18 15 12
63 56 52 46 35 24 23 18 15 12 10
98 63 56 52 46 35 24 23 18 15 12 10
98 63 56 52 46 35 29 24 23 18 15 12 10
98 63 56 52 46 35 32 29 24 23 18 15 12 10
98 90 63 56 52 46 35 32 29 24 23 18 15 12 10
98 90 63 56 52 46 45 35 32 29 24 23 18 15 12 10
98 90 64 63 56 52 46 45 35 32 29 24 23 18 15 12 10
98 90 64 63 56 52 46 45 35 32 29 24 23 18 15 12 10 8
98 90 64 63 56 52 46 45 35 32 29 24 23 18 16 15 12 10 8
98 90 82 64 63 56 52 46 45 35 32 29 24 23 18 16 15 12 10 8

課題

1.

プログラム名 OokiiJun21.java

上記のプログラムを完成させなさい

2.

プログラム名 OokiiJun22.java

上記のプログラムを完成させなさい

3.

OokiiJun22.java を改良して、引数としてファイル名を指定できるようにしなさい。つまり、

$ java OokiiJun23 data01.txt

で20件のソート

$ java OokiiJun23 data11.txt

で1101件のソート

プログラム名 OokiiJun23.java

まずは、使わなくても、

        int[] data = new int[1200];

などど大きな配列を用意する

表示はOokiiJun22.javaで25件を越えると25までしか表示しないようになっている。

できあがったら、最初と最後の20件を表示するように改良してみなさい。

もくじ

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