第8回 - ソート(1)

Go to Outline

課題1: 分割コンパイル

規模の大きなプログラムを作成しようとする場合，関数を単位としてソースコードを分割し，複数のファイルに分けてコンパイルすることができる．これを分割コンパイルと呼ぶ．

たとえば，prog7-1.c をコンパイルして，実行ファイル prog7-1 を生成するためには，以下のようにコンパイルした．

% gcc prog7-1.c -o prog7-1

これに対して，分割コンパイルでは，ソースファイルごとにコンパイルを行い，オブジェクトファイルを生成する．その後，必要なすべてのオブジェクトファイルをリンクして実行ファイルを生成する．分割コンパイルの例を以下に示す．

% gcc -c sort-check.c
% gcc prog8-1.c sort-check.o -o prog8-1

まず，ソースファイル sort-check.c をコンパイルすることで，オブジェクトファイル sort-check.o を生成する．その後，ソースファイル prog8-1.c をコンパイルし，生成しておいたオブジェクトファイルとリンクすることで，実行ファイル prog8-1 を生成する．

分割コンパイルを行う際には，関数プロトタイプによる宣言が必要であることに注意しなければならない．たとえば，ヘッダファイル sort-common.h には，以下のように関数プロトタイプの宣言が記述されている．

extern void print(struct data data[], int num);
extern int is_sorted(struct data data[], int num);

extern は，それが付与された関数や変数が外部オブジェクトファイルに宣言されていることを表している．

さらに，ヘッダファイル sort-common.h を見ると，以下のように構造体が定義されていることがわかる．

struct data {
    int key;
    char value;
};

sort-common.h を利用するためには，以下のようにインクルードする(取り込む)．

#include "sort-common.h"

prog8-1.c を実際に分割コンパイルして，prog8-1 を生成せよ．さらに，実行結果を確認せよ．

Makefile を用意しておいたので，それを利用するとコンパイルが楽になる．

課題2: バブルソート

ソート(sorting)とは，コレクションに格納された要素を，それぞれの要素のキーの値に基づき，一定の順序に並び替える作業のことである．キーの値が順に並べることを昇順(ascending order)のソート，キーの値が大きい順に並べることを降順(descending order)のソートと呼ぶ．

並び替え対象の配列に格納された隣り合う要素のキーの値を比較し，それらの要素を交換する作業を繰り返すことで，配列の要素全体を並び替える方法をバブルソート(bubble sort)と呼ぶ．

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

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

を持つソースコード prog8-2.c を作成する．data[0]〜data[num-1] の要素が並び替えの対象となる．

上記の関数を持つ prog8-2.c を作成せよ．

本課題では，テスト関数 test1() がすでに用意されている．ソートの動作を検査するテストコードを prog8-2.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);

課題3: 選択ソート

並び替え対象の配列の部分列に格納された要素の中でキーの値が最も小さい(大きい)要素を見つけ，それを部分列の先頭と交換する作業を繰り返すことで，配列の要素全体を並び替える方法を選択ソート(selection sort)と呼ぶ．

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

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

を持つソースコード prog8-3.c を作成する．a[0]〜a[num-1] の要素が並び替えの対象となる．

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

同一のキーの値を持つ要素に対して，それらの順序が維持されることが保証されているとき，ソートのアルゴリズムは安定(stable)であるという．

課題1のバブルソートでは隣接する要素のみを交換するので(同じキーの値を持つ要素を交換しないように実装されていれば)，安定である．一方で，選択ソートでは，隣接しない要素を交換した際に，もとの順序が維持される保証がないため，安定ではない．

選択ソートが安定でない場面を示すテストを用意して確認せよ．

課題4: 挿入ソート

並び替え対象の配列に格納された要素のキーの値に応じて，その要素をそれより前側の適切な位置に挿入する作業を繰り返すことで，配列の要素全体を並び替える方法を挿入ソート(insertion sort)と呼ぶ．

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

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

を持つソースコード prog8-4.c を作成する．a[0]〜a[num-1] の要素が並び替えの対象となる．

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

挿入ソートは安定かどうかを考えよ．

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

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

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

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

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

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

のコードを prog8-2.c，prog8-3.c，prog8-4.c から prog8-5.c にコピーすればよい．

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

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