アルゴリズム - クイックソート

はじめに

「見た目は 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 quicksort(a, first, last) {
    var i = first;
    var j = last;
    var x = a[(first + last) / 2];
    while (true) {
        while (a[i] < x) i++;
        while (x < a[j]) j--;
        if (i >= j) break;

        [a[i], a[j]] = [a[j], a[i]];
        ++i; --j;
    }
    if (first  < i - 1)
        quicksort(a, first , i - 1);
    if (j + 1 < last)
        quicksort(a, j + 1, last);
}

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

結果

Before: 33 17  3 50 33 25 57 72 46 93 82 72 49 84 78 86 74 23 95 26
After:   3 17 23 25 26 33 33 46 49 50 57 72 72 74 78 82 84 86 93 95

おわりに

Array.sort(ary, compfunc) と Binary.sort(bin, compfunc) はクイックソートです。また Binary のほうは compfunc が省略された場合に stdlib.h の qsort を使うように最適化されています。

...ということは、もしかすると Binary に対しての降順ソートは bin.sort(&(a, b) => b <=> a) よりも bin.sort().reverse() としたほうが速いのかも。Binary.reverse() も C ルーチンなので。ということでお試し。

function test(name, f) {
    var tmr = new SystemTimer();
    var sorted = f();
    var disp = [sorted[0], sorted[1], "...", sorted[-1]];
    System.println("%{name}%{disp} => ", tmr.elapsed());
}

var a = 10000.times(&() => Integer.parseInt(Math.random() * 100));
var bin = <...a>;
test("sort1", &() => bin.sort(&(a, b) => b <=> a));
test("sort2", &() => bin.sort().reverse());

sort1[99, 99, "...", 0] => 0.045096
sort2[99, 99, "...", 0] => 0.000582

...やはり。ではでは、また次回。