第31章 ソートに挑戦!  


今回は、データのソートの基礎です。ソートとは並べ替えのことです。 これも、どんな入門書にも書いてあります。まずは、5つのデータを 入力して、これを並べ替えて出力するプログラムを作ってみましょう。 一度に完成させるのは難しいので、まずは5つの整数を入力して それをそのまま出力するプログラムを作ります。

main関数では、(1)データ入力をする関数(2)並べ替え関数(3)結果表示 関数(いずれも自作関数)を順に呼び出すようにします。並べ替えは まだしないので、(2)の関数はreturnのみです。

#include <stdio.h> void input_data(long *); void sort_data(long *); void show_result(long *); int main(void) { long data[5]; input_data(data);//データ入力関数 sort_data(data);//並べ替え関数 show_result(data);//結果表示関数 return 0; } void input_data(long *x) { int i; printf("\n整数値を5個入力してください\n"); for (i = 0; i <= 4; i++) { printf("data[%d]=", i); scanf("%ld", (x + i)); //配列とポインタの所を復習してください } return; } void sort_data(long *x) { return; } void show_result(long *x) { int i; for (i = 0; i <= 4; i++) printf("data[%d] = %ld\n", i, x[i]); return; }

このように、少し面倒なプログラムの時は、 一度に完成させるのではなく、必要な部分を 少しずつ作っていくようにしましょう。 そのためにも、 何でもかんでもmain関数に書く 習慣は改めた方がいいかもしれません。(よけいなお世話だって!?)

それぞれの関数に仕事を分散させたので、データを 各関数に渡して処理しなくてはいけません。 一番簡単なのは、データをグローバル変数にしてしまい どこからでも参照できるようにすることです。 でもせっかく配列とポインタの勉強をしたのでそれを使って みましょう。また、関数に変数を渡すときそのまま渡したのでは 渡された方の関数は参照はできるものの、加工はできません。 関数に渡すときは、アドレスを渡しましょう。上のプログラムを よく見てください。意味が分からないときは、「配列とポインタ」 の所を復習してください。このプログラムの実行結果を下に示します。

入力した数字がそのままの順番で表示されています。

では、並べ替え部分について考えましょう。これも昔から いくつかのアルゴリズムがあって、代表的なものは 入門書にも必ず1つや2つは載っています。ここでは、 もっとも古典的な方法でやってみましょう。 sort_data()関数は、long型配列のアドレスを渡されました。 従って、この関数内からデータを書き換えることができます。 2つのデータを比較して大きい方を配列の番号の小さいものに 交換していけばよいことになります。そこで、次にデータを交換 する関数を考えてみましょう。これも、100%入門書に 書かれています。 もしかいていない本があればゴミ箱に捨てましょう!

//どんな本にでも載っているプログラム #include <stdio.h> void change_data(int *, int *); int main(void) { int x = 10, y = 5; printf("x=%d, y=%d\n", x, y); printf("データを交換します。\n"); change_data(&x, &y); printf("x=%d, y=%d\n", x, y); return 0; } void change_data(int *a, int *b) { int c; c = *a; *a = *b; *b = c; return; }

当ホーム・ページの読者のみなさんにこのプログラムの解説は 不要ですね。実行結果を下に示します。

ちゃんと、データが入れ替わっていますね。 このchange_data()関数をintの所をlongにすれば そのまま使えそうです。

では、ソートについて考えてみましょう。data[0],data[1], data[2],data[3],data[4]と5つのデータがあるとします。

手順 (1)data[0]とdata[1]を比較する (2)もしdata[1]の方が大きければ交換する (3)data[0]とdata[2]を比較する (4)もしdata[2]の方が大きければ交換する (5)data[0]とdata[3]を比較する (6)もしdata[3]の方が大きければ交換する (7)data[0]とdata[4]を比較する (8)もしdata[4]の方が大きければ交換する このような手順を踏むとdata[0]に一番大きい 値が入るはずである。次は、data[1]から data[4]までについて同じことをする。 そうすればdata[1]に2番目に大きい数値が入る。 次にdata[2]からdata[4]までについて同様の 操作をする。そうするとdata[2]に3番目に 大きい数値が入る。 以下同様である。

上の手順をプログラムすればよいですね。 では、sort_data(),change_data()関数を 作ってみましょう。

void sort_data(long *x) { int i, j; for (i = 0; i <= 3; i++) { for (j = i + 1; j <= 4; j++) { if (x[i] < x[j]) change_data(x + i, x + j); //x+iの意味をよく考えてください } } return; } void change_data(long *a, long *b) { long c; c = *a; *a = *b; *b = c; return; }

上の2つの関数を最初のプログラムに追加しましょう。 関数のプロトタイプ宣言も忘れないでください。 では、実行してみましょう。

見事に成功しましたね。今度は、データが5個ではなく 任意の個数に対応したプログラムを作ってみてください。 また、整数だけでなく文字をアイウエオ順に並び替えるような プログラムにも挑戦してみてください。


[Index][総合Index] [Previous Chapter] [Next Chapter]

Update Nov/25/1996 By Y.Kumei
当ホーム・ページの一部または全部を無断で複写、複製、 転載あるいはコンピュータ等のファイルに保存することを禁じます。