アルゴリズムを考える

目的

数の並び替えにどのくらい時間がかかるか調べてみる．いくつかのアルゴリズムを試す．効率的なアルゴリズムを設計する必要があることを感じ取る．

準備

教科書のプログラム（すこしだけ改編しています）：
bubblesort.c (p.212)， mergesort.c (p.223)
確認してみてください．

はじまり

10000 個の乱数の並び替え
bubblesort2.c， mergesort2.c，
並び替える数字をどう作っているかは，ソースコードを読んでみる．

time というコマンドを使い，実行に費やした時間を測ってみる．

% gcc bubblesort2.c
% time ./a.out

とするだけ．

...
4,998833,998966,999192,999331,999436,999531,999676,999798,134514086}
0.740u 0.000s 0:00.81 91.3%     0+0k 0+0io 77pf+0w

結果をどう解釈するか．

0.740u 0.000s 0:00.81 91.3%     0+0k 0+0io 77pf+0w
  (1)   (2)    (3)     (4)      (5)   (6)   (7)

(1) ... ユーザCPU時間( 0.74 秒) ．  要するに計算時間
(2) ... システムCPU時間(0.000秒)
(3) ... 経過時間(0.81秒) ． コマンドを起動してから終了するまでの経過時間．実時間
(4) ... 使用された資源率(91.3%=((1)+(2)/(3)))
(5) ... システムメモリ量＋利用者メモリ量(kB)
(6) ... ファイルの書き込み回数＋読み込み回数(ここではともに0回)
(7) ... ページフォルト(pf)回数＋スワップアウト回数

(5) が 0 というのはちょっとおかしいかもしれない...

この time コマンドは，

% which time
time: シェルに入っているコマンドです.

となっているはず． csh, tcsh を利用していない場合は， /usr/bin/time コマンドが動いたかもしれない．その場合は

% /usr/bin/time ./a.out
...

0.73user 0.01system 0:00.82elapsed 89%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (79major+18minor)pagefaults 0swaps

などと出力されているはず．

(1) ... ユーザCPU時間( 0.73 秒)
(2) ... システムCPU時間(0.01秒)
(3) ... 経過時間(0.82秒)

mergesort2.c をコンパイルし，同様に計測してみる．
アルゴリズム