Math Battle [ 0321: 0307の回答 ① ]

[ 0321: 0307の回答 ① ]

[ 大宙乗児君の回答 ]

授業再開後あれこれ他の科目の勉強も忙しくなって、つい回答が遅れました。

疾矢君さんと Skype で話し合い、評価対象のアルゴリズムを次の 3 種類に決めました。

　▪ QuickSort
　▪ MergeSort
　▪ HeapSort

まず QuickSort です。Perl で書いたソースコードは以下のとおり。
大小比較が何回おこなわれたかを調べるカウントを入れました。

#!/usr/local/bin/perl

$N = 100; # 100 から 1000 まで変えて実行。

@data = (
　# 1000 個の乱数 (整数)
);

$count = 0;

quickSort(0, $N-1);
printf("Count %d\n", $count);

sub quickSort($low, $high) {
　my ($low, $high) = @_;
　my $pi;

　$count++;
　if ($low < $high) {
　　$pi = partition($low, $high);
　　quickSort($low, $pi-1);
　　quickSort($pi+1, $high);
　}
}

sub partition ($low, $high) {
　my ($low, $high) = @_;
　my $pivot, $i, $tmp;

　$pivot = $data[$high];
　$i = ($low - 1);

　for ($j = $low; $j <= $high-1; $j++) {
　　$count++;
　　if ($data[j] < $pivot) {
　　　$i++;
　　　$tmp = $data[$i];
　　　$data[$i] = $data[$j];
　　　$data[$j] = $tmp;
　　}
　}
　$tmp = $data[$i+1];
　$data[$i+1] = $data[$high];
　$data[$high] = $tmp;
　return($i+1);
}

データ個数を 100, 200, 300, 400, ..., 1000 にした場合の実行時間をプロットしました。
O (nlogn) と言えるかどうかわかりません。リニア (linear) でないことはわかります。
やはり、その瞬間のパソコンの状態によって実行時間が影響を受けています。
きれいなグラフにはなりませんでした。