前回の再帰処理の再帰方程式をたてた処理時間予測の話の次として、 クイックソートの処理時間について解説を行う。 といっても、直感的に分かりにくいので、同じ アルゴリズムのマージソートを使って説明。 後半では、次に説明する動的メモリの説明の前説として、 C言語の固定サイズ配列のメモリ使用効率の悪さを説明する。

マージソートとは、与えられたデータを2分割し、それぞれをマージソート処理で 並び替え、その2つのデータの先頭から比べて大きいほうから格納しなおすアルゴリズム。 このため、再帰方程式は、以下のようになり、

代入を繰り返すことで一般式として、 を導きだすことができる。

この後、クイックソートと最大選択法の比較として、データ件数に応じた アルゴリズムを選択するための考え方を示す。 例えば、最大選択法で100件で2msec、クイックソートで同じく100件で1msec で処理が可能だった場合、何件以上であればクイックソートを使うべきか… という分析方法を示す。

よって、 =0.2μsec, =5μsec
よって、クイックソートの処理時間の一般式と、最大選択の一般式を イコールとして求まったデータ件数が、分岐点となる。 これを解くと、25=N/log N を満たすNであり、ニュートン法などで解けば、 この例ではN=40ぐらいとなる。 よって、40件以上ではクイックソートを採用すべきという結論が導ける。

このことから、一般的なC言語の組み込み関数のqsortなどでも、 データ件数が少なくなってくると、 O(N^2)のアルゴリズムに切り替えるようにプログラムされている。

C言語の固定サイズ配列の問題点

次に、固定サイズ配列の大きさの問題点を説明するために、 「名前と電話番号のデータベースを作りたい。宣言は？」 と聞いてプログラムを書いてもらい、その問題点を説明。

struct DataA {
char name[ 20 ] ;
int   phone ; // 09020932925は2^31より大きい
} table[ 45 ] ;
struct DataB {
char name[ 10 ] ;
char phone[ 12 ] ; // (0778)-27-2925#1234##
} table[ 100 ] ;

電話番号だってトーン機能を使うことも考えたら、12桁では足りないし、 名前も漢字5文字だったら、16bit×5=10byte で、足りないかも。 ひねくれた話をすれば、名前がジュゲムだったらどうするのとか、 1クラスではなく、1学年、1学科、1学校とかになれば、 配列は足りないし、使う可能性も低いのに配列サイズに巨大な値を 使えば、メモリ不足が発生する。

ということで次週にmallocなどを説明予定。