Kinx アルゴリズム - マージソート

アルゴリズム - マージソート

はじめに

「見た目は 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)$
  • 安定

テスト・ドライバ

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

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 mergesort(a, first, last) {
    var middle, work = [];
    var i, j, k, p;

    if (first < last) {
        middle = Integer.parseInt((first + last) / 2);
        mergesort(a, first, middle);
        mergesort(a, middle + 1, last);
        p = 0;
        for (i = first; i <= middle; i++) {
            work[p++] = a[i];
        }
        i = middle + 1;
        j = 0;
        k = first;
        while (i <= last && j < p) {
            if (work[j] <= a[i]) {
                a[k++] = work[j++];
            } else {
                a[k++] = a[i++];
            }
        }
        while (j < p) {
            a[k++] = work[j++];
        }
    }
}

demo(20, &(a) => {
    mergesort(a, 0, a.length() - 1);
    return a;
});

結果

Before:  4 84 51 71 19 44  6 90  4 22 13  0 41 15 36 73 79 50 97 64
After:   0  4  4  6 13 15 19 22 36 41 44 50 51 64 71 73 79 84 90 97

おわりに

マージソートは安定です。安定で平均して速いので魅力的ですが、ランダムなデータに対しては（不安定で良ければ） クイックソート のほうが速い。また外部にワーク領域が必要なので外部ソートです。

ではまた、次回。