Math Battle [ 0323: 0307の回答 ③ ]

[ 0323: 0307の回答 ③ ]

[ 大宙乗児君の回答 ]

最後の HeapSort です。これは追加のデータ領域を必要としません。
ソースコードは以下のとおりです。

#!/usr/local/bin/perl

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

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

$count = 0;

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

sub Sort() {
　my $n = $N;
　my $tmp;

　for ($i = $n/2 - 1; $i >= 0; $i--) {
　　heapify($n, $i);
　}
　for ($i = $n - 1; $i > 0; $i--) {
　　$tmp = $data[0];
　　$data[0] = $data[$i];
　　$data[$i] = $tmp;
　　heapify($i, 0);
　}
}

sub heapify($n, $i) {
　my ($n, $i) = @_;
　my $largest, $l, $r, $swap;

　$largest = $i;
　$l = 2*$i + 1;
　$r = $l + 1;

　$count += 2;
　if (($l < $n) && ($data[$l] > $data[$largest])) {
　　$largest = $l;
　}
　$count += 2;
　if (($r < $n) && ($data[$r] > $data[$largest])) {
　　$largest = $r;
　}

　$count++;
　if ($largest != $i) {
　　$swap = $data[$i];
　　$data[$i] = $data[$largest];
　　$data[$largest] = $swap;
　　heapify($n, $largest);
　}
}

大小比較演算のカウントをプロットしました。MergeSort と同様にほぼ直線ですね。