アルゴリズム - ヒープソート

はじめに

「見た目は JavaScript、頭脳(中身)は Ruby、（安定感は AC/DC）」 でお届けしているスクリプト言語 Kinx。「プログラム＝アルゴリズム＋データ構造」。アルゴリズムの実装例をご紹介。

元ネタは「C言語による（30年経っても）最新アルゴリズム事典」。今回はソート（ヒープソート）です。

参考
- 最初の動機 ... スクリプト言語 KINX（ご紹介）
  - 個別記事へのリンクは全てここに集約してあります。
- リポジトリ ... https://github.com/Kray-G/kinx
  - Pull Request 等お待ちしております。

アルゴリズムと言えばソート。ヒープソート。

ヒープソート

https://ja.wikipedia.org/wiki/ヒープソート
- 平均的にはクイックソートより遅いが最悪でも $O(n \log n)$
- 最悪でも $O(n \log n)$
- 安定ではない

テスト・ドライバ

テスト・ドライバコードは前回と一緒です。

function display(name, a) {
    System.println(name, a.map(&(e) => "%2d" % e).join(' '));
}

function demo(N, func) {
    var a = N.times(&() => Integer.parseInt(Math.random() * 100));
    display("Before: ", a);
    a = func(a);
    display("After:  ", a);
}

サンプル・コード

function heapsort(n, a) {
    var i, j, k, x;

    for (k = Integer.parseInt(n / 2); k >= 1; k--) {
        i = k;  x = a[i];
        while ((j = 2 * i) <= n) {
            if (j < n && a[j] < a[j + 1]) j++;
            if (x >= a[j]) break;
            a[i] = a[j];  i = j;
        }
        a[i] = x;
    }
    while (n > 1) {
        x = a[n];  a[n] = a[1];  n--;
        i = 1;
        while ((j = 2 * i) <= n) {
            if (j < n && a[j] < a[j + 1]) j++;
            if (x >= a[j]) break;
            a[i] = a[j];  i = j;
        }
        a[i] = x;
    }
}

demo(20, &(a) => {
    a = [0, ...a];
    heapsort(a.length() - 1, a);
    a.shift();
    return a;
});

結果

Before: 95 57 25 75 22 82 42 78 99 17 16 29 75 72  0  5 98  6 27 71
After:   0  5  6 16 17 22 25 27 29 42 57 71 72 75 75 78 82 95 98 99

おわりに

これまた元ソース（C言語）からほとんど修正していない。これだけでも目標達成だ。

ただ、ヒープソートの場合、原書（←私のは25年前に買った本、現在でも同じ記述なのかは未確認）にもあるように、添え字は 1 から始めるほうが自然なソースコードなので、あえて先頭要素にダミーデータを追加して最後に取る、という感じになってます。添え字を適宜 +1 する形でソースを書けばこの処理は不要（本来は無駄な処理）。今回は元ソースをそのまま使ったために、そう対応しただけなので。

ではまた、次回。

Kinx アルゴリズム - ヒープソート