配列の応用

配列の要素の最大値を求める

配列の応用として、配列要素の中から最大値を求めるプログラムを作ってみましょう。 ArraySample03は、5人の生徒のテストの得点を表示してから、最高得点を取った生徒の番号とその得点を表示するプログラムです。

ArraySample03.java
class ArraySample03 {
    public static void main(String[] args) {
        int[] a = {64, 75, 40, 92, 58};

        for(int i = 0; i < a.length; i++){
            System.out.println((i + 1) + "番の人の得点は" + a[i] + "点です。");
        }

        int imax = 0;
        for(int i =1 ; i < a.length; i++){
            if(a[i] > a[imax]){
                imax = i;
            }
        }
        System.out.println("最高得点は" + (imax + 1) + "番の人の" + a[imax] + "点です。");
    }
}
ArraySample03の実行結果
1番の人の得点は64点です。
2番の人の得点は75点です。
3番の人の得点は40点です。
4番の人の得点は92点です。
5番の人の得点は58点です。
最高得点は4番の人の92点です。

int型の変数imaxには、最終的には、配列全体での最大値となっている最初の要素のインデックスが格納されることになります。 最初は、a[0]を最大値と見なします。 つまり、imaxに0を代入しておくのです。 

        int imax = 0;

その次のfor文は、iの値が1で始まるので、まずa[1]と現在の最大値となっているa[0]が比較されます。 

        for(int i =1 ; i < a.length; i++){
            if(a[i] > a[imax]){
                imax = i;
            }
        }

この結果、a[1]の方が大きいので、最大値はa[0]からa[1]に交代することになります。 つまり、imaxに1が代入されることになります。 次はa[2]と現在の最大値であるa[1]が比較され、a[1]の方が大きいので、最大値はa[1]のままとなります。 つまり、imaxの値は1のままです。 このようにして、iを1からa.length-1までインクリメントしながら同様の処理を繰り返していきます。 そうすれば、最終的には、配列全体での最大値となっている要素のインデックスが、imaxに格納されていることになります。

その様子を図 8-4に詳しく示しておきます。

図 8-4 : 配列の要素の最大値を求める

配列の要素をソートする

複数のデータをその大きさに応じて並べ替えることをソート（sort）と言います。 そして、大きいものから小さいものへ並べることを降順ソート、小さいものから大きいものへ並べることを昇順ソートと言います。

ここでは、配列に格納されたテストの得点を高い方から低い方へ並べ替えるプログラムを見てみましょう。

ArraySample04.java
class ArraySample04 {
    public static void main(String[] args) {
        int[] a = {64, 75, 40, 92, 58};

        for(int i = 0; i < a.length-1; i++){
            for(int j = i+1; j < a.length; j++){
                if(a[j] > a[i]){
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
        }

        for(int i = 0; i < a.length; i++){
            System.out.println((i + 1) + "位の人の得点は" + a[i] + "点です。");
        }
    }
}
ArraySample04の実行結果
1位の人の得点は92点です。
2位の人の得点は75点です。
3位の人の得点は64点です。
4位の人の得点は58点です。
5位の人の得点は40点です。

ソートのアルゴリズムには様々なものが有りますが、ArraySample04では基本選択法（selection sort）というアルゴリズムを利用しています。

ソートを実行しているのは、for文による二重ループの部分です。 そこでの処理の手順は次のようになります。

  1. まず、iの値が0のときは、a[0]とa[1]を比較して、a[1]の値の方が大きいならば、a[0]とa[1]の値を交換します。 さらにa[0]とa[2]、a[0]とa[3]、a[0]とa[4]についても同様の処理をします。 この結果、a[0]には一番大きな値が格納されることになります。 この時点で、a[0]の値は確定したことになります。
  2. iの値が1のときは、a[1]とa[2]を比較して、a[2]の値の方が大きいならば、a[1]とa[2]の値を交換します。 さらにa[1]とa[3]、a[1]とa[4]についても同様の処理をします。 この結果、a[1]には2番目に大きな値が格納されることになります。 この時点で、a[1]の値は確定したことになります。
  3. iの値が2のときは、a[2]とa[3]を比較して、a[3]の値の方が大きいならば、a[2]とa[3]の値を交換します。 さらにa[2]とa[4]についても同様の処理をします。 この結果、a[2]には3番目に大きな値が格納されることになります。 この時点で、a[2]の値は確定したことになります。
  4. iの値が3のときは、a[3]とa[4]を比較して、a[4]の値の方が大きいならば、a[3]とa[4]の値を交換します。 この結果、a[3]には4番目に大きな値が格納されることになります。 この時点で、a[3]の値は確定したことになります。
  5. そして、残ったa[4]には既に一番小さい値が入っているので、a[4]の値もこれで確定です。

実際に要素の値を交換しているのは、次の部分です。 

                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;

一般に、変数a, bの値を交換するプログラムは、次のようになります。 

                    int temp = a;
                    a = b;
                    b = temp;

次のようにするのは間違いです。 

                    a = b;
                    b = a;

これだと、aには確かにbの値が代入されますが、そのaの値をbに代入しているので、bの値は元のままになってしまいます。 「int temp = a;」のように、aの値を一時的に保存しておく必要があるのです。

ArraySample04の二重ループでの実際の処理の流れについては、図 8-5を見て確認してください。

図 8-5 : 配列の要素をソートする