[目次] [前回] [次回] [重要語索引]

第6週： 複雑な繰り返し

6. 1 ソーティング
6. 2 最小のデータを探す
6. 3 練習問題
6. 4 値の入れ替え
6. 5 配列の内容の表示
6. 6 練習問題
6. 7 組になったデータのソーティング
6. 8 宿題
6. 9 おまけ

6.1 ソーティング

データをある順序で並べ替えることをソート(sort)するといいます。ここで「ある順序」とは、数値なら大きい順、小さい順、文字列ならアルファベット順など、2つのデータを比較してどちらが前に来るかがはっきり分かれば、どんなものでも構いません。

例えば、次のような5個の数値を小さい順に並べ替えることを考えてみましょう。

sort-1

まず、一番小さい数値を見つけて、それを一番目に持ってきます。

sort-2

次に、残った中で一番小さい数値を見つけて、それを二番目に持ってきます。

sort-3

これを残りが無くなるまで繰り返せばよいのですが、

という問題があるので、次のように、データをうまく移し変えるようにします。

このやり方をもっと正確に書いてみましょう。

  1. 変数 n の値を 0 とする。
  2. 配列の [n] 以降の部分で、最小のデータを探し、その添字を m とする。
  3. [n] のデータと [m] のデータを入れ替える。
  4. n を 1 増やす。
  5. [n] が最後のデータならこれで終了し、そうでなければ 2 に戻って繰り返す。
このように、計算のやり方を正確に書いたものをアルゴリズム(algorithm)と呼びます。アルゴリズムが分からなければ、プログラムを書くことはできません。

上のアルゴリズムからプログラムを作るには、「最小のデータを探す」や「入れ替える」というところも、アルゴリズムを明らかにする必要があります。

これからプログラムを少しずつ作っていきます。SfcTemplate1.java,SfcTemplate1.html を Sort.java, Sort.html にコピーして準備しましょう。

6.2 最小のデータを探す

これは前回やりました。前回は2次元配列でしたが、1次元配列(普通の配列)の場合のアルゴリズムは次のようになります。

  1. 探索途中の暫定的な最小値の添字を覚えておく変数を minIndex とする。最初は、配列の [0] のデータを暫定的に最小値とする。
  2. 変数 i の値を 1 とする。( [0] のデータはすでに暫定最小値なので)
  3. [i] のデータと、今のところ暫定最小値の [minIndex] を比べる。
  4. [i] のデータの方が小さければ、それを新しい暫定最小値にする。
  5. [minIndex] の方が小さければ、何もしない。
  6. i の値を 1 増やす。
  7. もうデータが無ければ、終了。そうでなければ、3 に戻って繰り返す。

このアルゴリズムをプログラムにすると、次のようになります。 
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

    void sfcProcess () {
	//ここに自分のプログラムを書く
	int a[] = { 17, 23, 10, 32, 13 };
	int i = searchMin(a);
	sfcOutput("a["+String.valueOf(i)+"] : "+String.valueOf(a[i]));
    }

    int searchMin (int a[]) {
	int minIndex = 0;
	for ( int i = 1; i < 5; i = i + 1 ) {
	    if ( a[minIndex] > a[i] ) {
		minIndex = i;
	    }
	}
	return minIndex;
    }

6.3 練習問題

上のアルゴリズムとプログラムは、配列全体の最小値を探します。しかし、ソートのプログラムで使うには、[n] 以降のデータの最小値を探す必要があります。そのようにプログラムを変更しなさい。例えば、[3]以降の最小値を探したいときは、46行目を 

    int i = searchMin(a, 3);
と変更すると、a[4] : 13 と表示される、ということです。

6.4 値の入れ替え

次に、[n] のデータと [m] のデータを入れ替えるアルゴリズムを考えましょう。

a[n], a[m] の値を入れ替えるとき、 

    a[n] = a[m];
    a[m] = a[n];
としたのではうまくいきません。a[n] = a[m]; とした途端に、a[n]に入っていた値が消えてしまうからです。値を一時退避させるための変数を作って、次のようにします。 
    temp = a[n];
    a[n] = a[m];
    a[m] = temp;

6.5 配列の内容の表示

配列の内容を文字列に変換するアルゴリズムを考えましょう。

  1. String 型の変数 s に [0] のデータを文字列に直して入れる。
  2. 変数 i の値を1にする。([0]は既に済んでいるので)
  3. コンマと、[i] のデータを文字列に直したものを s の最後に追加する。
  4. 変数 i の値を1増やす。
  5. もうデータが無ければ、終了。そうでなければ3に戻って繰り返す。

String 型の変数 s に、コンマと a[i] の内容を追加するには 

    s = s + ", " + String.valueOf(a[i]);
とします。

6.6 練習問題

今までのアルゴリズムを組み合わせて、ソーティングのプログラムを完成させましょう。

  1. 結果が確認できるよう、配列の内容を出力するように変更します。
  2. 一番小さいデータを先頭のデータと入れ替えるには、どうすればよいでしょうか？
  3. 二番目以降に対しても次々と繰り返していくには、どうすればよいでしょうか？

6.7 組になったデータのソーティング

次のようなデータをソートすることを考えてみましょう。
Country Total Population
(in thousands, 1997 est.)		GDP
(million US$, 1995)
United Kingdom 58201 1102658
Egypt 64466 60436
India 960178 338785
Japan 125638 5217573
Australia 18250 358147
United States of America 271648 6954787
Brazil 163132 717187
(出典：http://www.un.org/Pubs/CyberSchoolBus/infonation/e_infonation.htm)

このデータをそのままグラフにするプログラムは次のようになります。SfcTemplate2.java, SfcTemplate2.html を Nation.java,Nation.html にコピーして、どのように表示されるか確認しましょう。 
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

    void sfcDraw(Graphics g) {
	//ここに自分のプログラムを書く
	String name[]    = {"UK", "Egypt", "India", "Japan", 
			    "Australia", "USA", "Brazil"};
	int population[] = {58201, 64466, 960178, 125638, 
			    18250, 271648, 163132};
	int gdp[]        = {1102658, 60436, 338785, 5217573, 
			    358147, 6954787, 717187};
	for (int i = 0; i < 7; i = i + 1) {
	    g.setColor(Color.black);
	    g.drawString(name[i], 10, i*35+30);
	    g.setColor(Color.blue);
	    g.fillRect(80, i*35+15, population[i]*200/1000000, 10);
	    g.setColor(Color.green);
	    g.fillRect(80, i*35+25, gdp[i]*200/7000000, 10);
	}
    }

6.8 宿題

上のデータを人口の多い順にソートして、グラフを描くプログラムを書きなさい。

6.9 おまけ

上のプログラムを改造し、入力として name、population、GDP のどれかを入れると、それぞれ国名のアルファベット順、人口の多い順、GDPの大きい順に並べ替えて、同じようにグラフを描くプログラムを書きなさい。

[目次] [前回] [次回] [重要語索引]

慶應義塾大学の授業以外での無断利用、複製はご遠慮下さい。
Copyright (c) 2000 慶應義塾大学