Kinx アルゴリズム - バブルソート

アルゴリズム - バブルソート

はじめに

「見た目は 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 bubblesort(n, a) {
    var k = n - 1;
    while (k >= 0) {
        var j = -1;
        for (var i = 1; i <= k; i++) {
            if (a[i - 1] > a[i]) {
                j = i - 1;
                [a[i], a[j]] = [a[j], a[i]];
            }
        }
        k = j;
    }
}

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

結果

Before: 87 50 94  9 30 62  4  2 31 10 59 85 46 46 58 83 24 44 27 33
After:   2  4  9 10 24 27 30 31 33 44 46 46 50 58 59 62 83 85 87 94

おわりに

さすがに C系統のシンタックス を目指しただけあって、元ネタ（C言語）のコードからほとんど修正せずに使えています。素晴らしい。

ではまた、次回。