配列あるいは構造体配列に記憶されたデータのうち，ある要素について，それ
を昇順あるいは降順に並べ替えることをソーティング(整列)といいます．ソー
ティングはサーチングを効率良く行うために必要とされる場合が多くあります．
ソーティングを実現するアルゴリズムとして，単純選択法，バブルソート法，
クイックソート法，バケットソート法などが知られています．各ソート法の概
念を図 10, 11, 12に示します．
Figure 12: クイックソート法(左)とバケットソート法(右)
練習問題 2-2 データファイルの内容を構造体配列に読み込み，座標原点からの距離が大きい 順に交差点名をソートし，結果を画面に出力するプログラムを作成しなさい． データのソートには，単純選択法を使用すること．
-----------------------
/* sort_simple.c --- 単純選択法によるデータのソート */
#include <stdio.h>
#include <math.h>
#define CrossingNumber ... /* 交差点数 */
... /* 構造体の定義 */
Crossing cross[CrossingNumber]; /* 交差点の変数宣言 */
...
void simple_sort(void)
{
int i, j, mx;
double x, y, xm, ym, distance, distance_max;
double distance_max_prev = 100.;
for (i = 0; i < CrossingNumber; i++) {
distance_max=-1;
for (j = 0; j < CrossingNumber; j++) {
x = cross[j].pos.x;
y = cross[j].pos.y;
distance = sqrt ( x * x + y * y);
... /* 求めた距離が distance_max_prev より小さく
distance_max より大きい場合，mx に j の値
を代入し，distance_max に distance の値を
代入する手続きを入力して下さい． */
}
.... /* mx 番目の交差点名および原点からの距離を出力する */
distance_max_prev=distance_max;
}
}
void main(void)
{
map_read("map.dat"); /* 地図情報の読み込み */
simple_sort(); /* ソーティングの実行 */
}
-----------------------
練習問題 2-3
データファイルの内容を構造体配列に読み込み，キーボードから入力した座標 に近い順に交差点名を画面に出力するプログラムを作成しなさい．データのソー トには，バブルソート法を使用すること．
-----------------------
/* bubble_sort.c --- バブルソート法によるデータのソート */
#include <stdio.h>
#include <math.h>
#define CrossingNumber ... /* 交差点数 */
... /* 構造体の定義 */
Crossing cross[CrossingNumber]; /* 交差点の変数宣言 */
...
void result_display(void)
{
int i;
for (i = 0; i < CrossingNumber; i++ ) {
... /* 交差点名の表示 */
}
}
void bubble_sort( double xo, double yo )
{
int lo, up, i, j;
lo = 0;
up = CrossingNumber - 1;
while ( up > lo ){
... /* PAD を参考にしてバブルソートを実現する
手続きを作成して下さい */
}
}
void main(void)
{
double xo, yo;
map_read("map.dat"); /* 地図情報の読み込み */
/* 距離を計算する際の原点を入力 */
printf("原点のＸ座標を入力して下さい\n");
... /* 基準になる地点のＸ座標の入力 */
printf("原点のＹ座標を入力して下さい\n");
... /* 基準になる地点のＹ座標の入力 */
bubble_sort(xo, yo); /* ソーティングの実行 */
result_display(); /* ソーティング結果の表示 */
}
-----------------------
練習問題 2-4
データファイルの内容を構造体配列に読み込み，キーボードから読み込んだ交 差点名と一致する交差点，およびそれに隣接する交差点の位置を2次元平面に 表示するプログラムを作成しなさい．2次元平面に点を表示するには，基礎編 で学習したグラフィック関数を使用すること．
-----------------------
/* Search_map.c --- データの検索と位置の表示 */
#include <stdio.h>
#include <math.h>
#include <Xtc.h>
#define CrossingNumber ... /* 交差点数 */
/* 座標変換マクロの定義 */
...
#define gx(x) ...
#define gy(y) ...
/* 構造体の定義 */
...
/* データ宣言 */
Crossing cross[CrossingNumber];
...
/* 交差点の表示 */
void map_show(int io)
{
setcolor(RED);
circle(gx(cross[io].pos.x), gy(cross[io].pos.y), 2);
... /* io 番の交差点に隣接する交差点の位置に青い円を
書く手続きを入力して下さい */
}
/* サーチングの実行 */
void search(int *io )
{
int i;
char item_search[20];
... /* 構造体配列の交差点名を表す要素と，検索する要素
の比較を行い，一致した場合配列の列番号を io
に代入する手続きを入力して下さい． */
}
void main(void)
{
int io;
map_read("map.dat"); /* 地図情報の読み込み */
search(&io); /* サーチングの実行 */
initgraph(); /* グラフィックス環境の初期化 */
map_show(io); /* 交差点の表示 */
xtcmainloop( 3 ); /* 終了入力待ち */
closegraph();
}
-----------------------
練習問題 2-5
データファイルの内容を構造体配列に読み込み，座標原点からの距離の度数分 布を表すグラフを作成しなさい．グラフを作成するためには，基礎編で学習し たグラフィック関数を用いるか，または，gnuplotを使用すること．
-----------------------
/* Sort_histogram.c --- 座標原点からの距離をヒストグラム化するプログラム */
#include <stdio.h>
#include <math.h>
#include <Xtc.h>
#define CrossingNumber ... /* 交差点数 */
... /* 構造体の定義 */
Crossing cross[CrossingNumber]; /* 交差点の変数宣言 */
int histogram[20];
/* ヒストグラムの表示 */
void hist_show(void)
{
... /* 配列 histogram の各要素の大きさをヒストグラ厶と
してグラフィック化する手続きを入力して下さい．
gnuplotを使用する場合，データをファイルへ書き出
す手続きを入力して下さい． */
}
/* ヒストグラムの作成 */
void histogram_insert( double distance )
{
int distance_int;
... /* 引数 distance を整数型変数 distance_int
に変換する．(四捨五入を用いること) */
... /* 配列 histogram の各要素が distance_int の
度数分布を表す手続きを入力して下さい． */
}
/* 座標原点からの距離の計算 */
void distance_cal( int i, double distance )
{
... /* 座標原点からの距離を計算する． */
}
void main(void)
{
int i;
double distance;
map_read("map.dat"); /* 地図情報の読み込み */
for( i = 0; i < CrossingNumber; i++) {
distance = distance_cal(i,distance); /* 座標原点からの距離計算 */
histogram_insert(distance); /* ヒストグラムの作成 */
}
initgraph(); /* グラフィックス環境の初期化 */
hist_show(); /* ヒストグラムの表示 */
xtcmainloop(3); /* 終了入力待ち */
closegraph();
}
-----------------------