ログイン
kid's world

データを整理する

データを整列する

データを何らかの規則に基づいて整列させなければならないという場合は多くあるだろう。

たとえば先ほどのテストの点数の例では,点数の高いもの順に並び換えるという場合が考えられる。

この並び換え,すなわちソートには,いろいろなアルゴリズムが存在している。自分だったらどのように並び換えを行うかを考えてみよう。

データがすでにほとんど整列している場合と,バラバラの場合とでは,きっと並び換えの方法は異なるだろう。それが証拠に,ほとんど整列しているときには高速に終了するアルゴリズムや,どんな順序で並んでいても同じ時間がかかるアルゴリズムなど,さまざまなアルゴリズムがあるのである。

いい換えれば,利用する場面に応じてさまざまなアルゴリズムを使い分ける必要があるということである。

選択整列法

ここでは,いちばん理解しやすい選択整列法について解説しよう。数値を大きいもの順に並び換える場合についての実際の例をFig. 7に描いたので,それを見ながら理解していただきたい。

Fig. 7: 選択整列法のイメージ

/c/algorithm-fig7.png

Fig. 7-(a)が初期状態である。まず全体の中から最大の値を選び出し,それを先頭のデータと置き換える。すると最大のデータが先頭に移動したことになるので,先頭の部分はこれで確定だ。よって,Fig. 7-(b)の状態になる(グレーの部分は確定した部分である)。

次に,確定した部分を除いた中で最大のものと,2番目のデータを交換する。最大の値は自分自身であり,自分自身と交換する。すなわち外見的にはそのまま確定となり,Fig. 7-(c)の状態に移ることになる。同様にして3番目のデータ,4番目のデータと続けて,Fig. 7-(e)の状態までなって最後の2つのデータの交換が終わったとき(交換が起こらない場合もあるが),すべてのデータは確定され,ソートが完了する。

フローチャート

選択整列法では,内部で最大値(または最小値)を求めるアルゴリズムを使っている。

これはすでに述べたところなので,フローチャートでは簡単に「最大値を求める」と記述する。また,値を交換するところも「交換する」と簡単に書いてしまおう。すると,このソートのアルゴリズムはFig. 8のように記述できる。

Fig. 8: 選択整列法のフローチャート

/c/algorithm-fig8.png

このように見てみると非常にシンプルだ。ところで,ループの条件を「49未満」として,ループの中では変数iは48までしか増えないようにしている理由はわかるだろうか。なぜなら,従来どおり「50未満」としても正常に動くのだが,最後の要素(すなわちa[49])は交換するとしても自分自身とするしか方法がなく,結果的に交換は起こらないのである。

したがって,配列の添え字が49まであってもiは48まででよいのである。

C言語による実装

では,実際にC言語でこのアルゴリズムを実装してみよう。今回のフローチャートは細かく描いていないので,少々翻訳にエネルギーを必要とするかもしれない。まず変数名をどのように決めるかから考えよう。

配列a,変数iとmはフローチャートの中に描いてあるのでそのまま使おう。問題は最大値を求めるときに使うループ変数だ。これには従来のようにiを使うことはできないので,jとしておこう。

ところで,「a[i]とa[m]の値を交換」するために,一時的に値を退避させておく変数が1つ必要となる。

単純に,

a[i]=a[m];
a[m]=a[i];

と書いてもいいような気がするが,これは誤りである。

1行目でa[i]の内容はa[m]の内容で上書きされて失われてしまう。したがって2行目の文は意味がなくなる。値を交換したいときは,一時的にa[i]の値を退避させなければならないのだ。退避に使う変数として,一時的という意味のtemporaryの頭文字をとった変数tを宣言しておこう。変数tを使えば,

t=a[i];
a[i]=a[m];
a[m]=t;

と書くことによって,値の交換ができるようになる。

以上のように変数名を決めて,実際のプログラムを組んだ例がList 2である。最大値を求めるにはfor文を使うため,for文の中にfor文が入るという構造になる。List 2-(1)の部分が,最大値を求めている部分で,List 2-(2)の部分が値の交換を行っている部分である。show_allという関数を作って,配列の内容を表示するようにした。実行結果は,Fig. 9を参照していただきたい。

List 2: 大きいもの順に並び変えるプログラム

#include <stdio.h>

void input_data(int data[]);
void show_all(int data[]);

void input_data(int data[])
{
  /* データ入力を行う(省略) */
}

void show_all(int data[])
{
  /* 配列の内容を表示する */

  int i;
  for(i=0; i<50; i++)
    printf("%d ", data[i]);
  
  printf("\n");
}

void main()
{
  int i, j, m, t, a[50];
  
  input_data(a);
  
  printf("整列前:");
  show_all(a);
  
  for(i=0; i<49; i++){
    for(j=i+1,m=i; j<50; j++){ |
      if(a[m]<a[j])            |
        m=j;                   |(1)
    }                          |
    
    t=a[i];                    |
    a[i]=a[m];                 |(2)
    a[m]=t;                    |
  }
  
  printf("整列後:");
  show_all(a);
}

Fig. 9: List 2の実行結果

/c/algorithm-fig9.png


構造体」へ進む

広告


©Toshio Koide 1996-2007.

目次

リンクについて

リンクは御自由にどうぞ。

メール

mail.gif

広告