アルゴリズム - 挿入ソート

はじめに

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

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

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

アルゴリズムと言えばソート。挿入ソート。

挿入ソート

https://ja.wikipedia.org/wiki/挿入ソート
- 遅いが単純、ただしほとんど整列済みのデータに対しては高速
- $O(n^2)$
- 安定

テスト・ドライバ

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

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 inssort(n, a) {
    var j;
    for (var i = 1; i < n; i++) {
        var x = a[i];
        for (j = i - 1; j >= 0 && a[j] > x; j--)
            a[j + 1] = a[j];
        a[j + 1] = x;
    }
}

demo(20, &(a) => {
    inssort(a.length(), a);
    return a;
});

結果

Before: 78  8 62 49 37 43 22 71 18 74 66 53  0 46 50 69 27  9 20 99
After:   0  8  9 18 20 22 27 37 43 46 49 50 53 62 66 69 71 74 78 99

おわりに

こちらも元ソース（C言語）からほとんど修正していない点は合格。しかも記載通り単純で実装が簡単。また、Kinx でも && は短絡演算子なので、j >= 0 && a[j] > x で j == -1 のとき a[j] は評価されないので問題はありません。

ではまた、次回。

Kinx アルゴリズム - 挿入ソート