第9回では，以下の項目に関して学ぶ．

  1. クイックソート
  2. マージソート
  3. シェルソート

課題のソースコードのテンプレート:

課題1: クイックソート

枢軸の値を基準として配列に格納された要素を2つのグループ(枢軸の値より小さなキーの値を持つ要素群と枢軸の値より大きなキーの値を持つ要素群)に分け，それぞれのグループで要素を再帰的に並び替えることで，配列全体を並び替える方法をクイックソート(quick sort)と呼ぶ．枢軸の値とキーの値が等しい場合は，どちらのグループに入れてもよい．

ここでは，sort-common.h で定義されている以下の構造体を扱う． 

struct data {
    int key;
    char value;
};

struct data 型の配列 data[] に格納された整数の値 key をキーとして，クイックソートにより配列の要素を昇順に並び替える関数 

void quick_sort(struct data data[], int num);
を持つソースコード prog9-1.c を作成する．a[0]〜a[num-1] の要素が並べ替えの対象となる．


上記の関数とテストコードを含む prog9-1.c を作成せよ．

ソートの実行結果を確認するため，ソースコード sort-check.c に以下に示す2つの関数を用意した．これらの関数を利用するには，sort-check.oをリンクすればよい．

(1) data[] の要素を画面に表示する．num はソート対象の配列の要素の数を指す．
void print(struct data data[], int num);
(2) data[] が昇順に並んでいるかどうかを検査する．num はソート対象の配列の要素の数を指す．昇順に並んでいる場合には 1，並んでいない場合には 0 を返す．
int is_sorted(struct data data[], int num);

課題2: マージソート

配列に格納された要素を2つのグループに分け，それぞれのグループで並び替えを実施する．並び替え後のグループを再帰的に結合することで，配列全体を並び替えるする方法をマージソート(merge sort)と呼ぶ．

sort-common.h で定義されている struct data 型の配列 data[] に格納された整数の値 key をキーとして，マージソートにより配列の要素を昇順に並び替える関数 

void merge_sort(struct data data[], int num);
を持つソースコード prog9-2.c を作成する．a[0]〜a[num-1] の要素が並べ替えの対象となる．


上記の関数とテストコードを含む prog9-2.c を作成せよ．

課題3: 線形リストを用いたマージソート

課題2のように配列を用いてマージリストを実現すると，もとの配列と同じ大きさの作業用の領域が別途必要になる．さらに，もとの配列の要素を作業用の領域にコピ−するコストも無視できない．

線形リストを用いることで，これらの欠点を回避することができる．そこで，sort-common4list.h で定義されている以下に示す構造体で線形リストを実現し，それをマージソートで利用することを考える． 

struct element {
    struct data data;
    struct element *next;
};
struct data は，課題1と同じ構造体である．

struct element 型のポインタ top が先頭の要素を指す線形リストに対して，struct data に格納された整数の値 key をキーとして，マージソートにより線形リストの要素を昇順に並び替える関数 

struct element *merge_sort(struct element *top);
を持つソースコード prog9-3.c を作成する．この関数の戻り値は，ソート後の線形リストの先頭の要素を指すポインタとする．


上記の関数とテストコードを含む prog9-3.c を作成せよ．

本課題では，テスト関数 test1() がすでに用意されている．ソートの動作を検査するテストコードを prog9-3.c に追加せよ．

ソートの実行結果を確認するため，ソースコード sort-check.c に以下に示す3つの関数を用意した．これらの関数を利用するには，sort-check.o をリンクすればよい．

(1) data[] から線形リストを生成する．num はソート対象の配列の要素の数を指す．
struct element *create_list(struct data data[], int num);
(2) top が先頭の要素を指す線形リストの要素を画面に表示する．
void print(struct element *top)
(3) top が先頭の要素を指す線形リストの要素が昇順に並んでいるかどうかを検査する．昇順に並んでいる場合には 1，並んでいない場合には 0 を返す．
int is_sorted(struct element *top);

課題4: シェルソート

挿入ソートでは，要素の挿入先が現在の位置と大きく離れていると，要素をずらすための代入が多くなる．たとえば，6番目に存在する要素を0番目に挿入する場合，その間に存在する要素をずらすための代入が5回行われる．

シェルソート(shell sort)では，並び替え対象の配列において，最初に h 個離れた要素(たとえば，h = 4 )をグループ化して大まかな並び替えを実施し，h の値を縮めていきながら並び替えを繰り返す(h = 4 の次は h = 2 のように縮めていく)ことで，要素をずらすための代入の回数を減らす．最終的に h = 1 となれば並び替えが完了する．

sort-common.h で定義されている struct data 型の配列 data[] に格納された整数の値 key をキーとして，シェルソートにより配列の要素を昇順に並び替える関数 

void shell_sort(struct data data[], int num);
を持つソースコード prog9-4.c を作成する．a[0]〜a[num-1] の要素が並べ替えの対象となる．


上記の関数とテストコードを含む prog9-4.c を作成せよ．
シェルソートでは，経験的に，h の値は 1 からはじめて，前の値を 3 倍して 1 を加えた数列( h = 1, 4, 13, 40, ...) が利用されている．

課題5: ソート時間の比較

課題1, 2, 4で作成した3種類のソートプログラムの実行時間を計測し，その結果について比較して考察せよ．

実行時間を計測するには，以下の3つの関数 

void quick_sort(struct data data[], int num);

void merge_sort(struct data data[], int num);

void shell_sort(struct data data[], int num);
のコードを prog9-1.c，prog9-2.c，prog9-4.c から prog9-5.c にコピーすればよい．


上記の3つの関数のコードをコピーして prog9-5.c を作成して，実行時間を計測せよ．

ソート対象の要素の数(SMALL_NUM，MEDIUM_NUM，LARGE_NUM の値)をいろいろ変更して，実行時間を計測するとよい．

Go to Top