整列３(所要時間)

どちらが速いか

時間の測定

●十進BASICには TIME という関数があります。これは深夜０時からの秒数を返すものです。整列の前に LET t0=TIME とでもして、開始の秒数を記録しておき、整列が終わったら、LET t1=TIME と求め、あとで t1-t0 を計算すれば所要時間を出すことができます。配列を用意する部分や結果を表示する部分は入れないようにして整列する時間だけを計りましょう。

●プログラムの流れは次のようになります。

数を配列に準備する。
LET  t0=TIME
整列する
LET  t1=TIME
整列の結果を表示する
PRINT t1-t0;"秒"

●ただしこの方法は日付の変わる０時を挟んで整列させた場合は正しい結果がでません。

乱数を使って数を準備する

●１０個しかないと、瞬時に整列が済みますのでどんな方法でもほとんど０秒になってしまいます。乱数を使ってたくさんの数を用意するようにしましょう。

●123.2456のような数でも整列できますが、うまくいったかどうかの確認のため、int関数で整数にして１〜1000あたりまでの数が並ぶようにします。

●input n でいくつ数をつくるか指定できるようにしました。

RANDOMIZE
INPUT n
DIM a(n)
FOR i=1 TO n
   LET  a(i)=INT(RND*1000)
NEXT i

●DATA を READ していた部分をこれで置き換えます。

●これにあわせて、整列や結果表示の部分も１０になっていた部分も n にしなければなりません。９とせずに10-1としていたのは、このときのことを考えていたのです。

計ってみよう

●time.txtに記入してBASIC内に提出

●10000個にもなると、整列もかかりますが、それ以上に結果の表示に時間がかかります。プログラムが完全に動くとわかったら表示を止めるようにするとよいでしょう。たとえば、

IF n < 1000 THEN
   FOR i=1 TO n
      PRINT a(i);
   NEXT i
END IF

結果の考察

●速さの評価は単純ではありません。数が少ないときは速いのですが、多くなるとだめなものとか、その逆もあります。また、元の数がばらばらだと速いけど、逆順に並んでいると極端に時間がかかるとか、だいたいそろっているときにとても速いなど、得意・不得意があります。

●選択ソートとバブルソートを比べたら、次に数値の数と時間の関係を見てください。数が２倍になると、時間は何倍になるかということです。

●選択ソートもバブルソートも数が２倍になると、時間は４倍、３倍になると９倍というように、x倍だとx²倍になることがわかっています。これをＯ(n²)などと表します。データの量が少ないうちはいいのですが、ある程度以上多くなってくると我慢できないほど遅くなってしまいます。