- 4 mergesort または quicksort を動かす. データ数 N を何通りかに変化させて時間も測る.
- 5 quicksort がN2 に比例する時間が掛かることを確認する.
- 6 ビンソートのプログラムを作成し, N と所要時間の関係を検討する.
- 7 基数ソートのプログラムを作成し, データ量と所要時間の関係を検討する.
- 8 ここで説明した以外の整列アルゴリズムを実装する.
Rubyの計算量を図るサイト を作成しました。
Reactで以下のように計算できるようにしました。
<Rben
Globals={['puts "hello"']}
Cases={['puts "world"']}
/>
各ソート関数に対し、Nが1から10000での処理時間 dt / ms を測定したところ以下の表を得ました。 また、課題8に対してはRubyが提供する既存のsort関数を試してみました。
| index | N=1 | N=10 | N=100 | N=1000 | N=10000 |
|---|---|---|---|---|---|
| bubble | 22 | 17 | 297 | 1192 | 7103 |
| quick | 19 | 19 | 21 | 45 | 229 |
| bin | 34 | 33 | 28 | 34 | 75 |
| radix | 22 | 19 | 78 | 215 | 361 |
| sort | 21 | 17 | 21 | 20 | 30 |
bubbleとradixはNに対し大きく時間がかかるようになりました。 これはn^2の計算時間を要するためであると考えられます。 今回Wasmを用いたので，コードの読み込み自体に約20ms程かかっているので、 そのことを考慮すると，~100ではほとんど影響が見られないといえます。 また，defaultで定義されているsortが非常に早いことがわかりました。