アルゴリズム - 選択ソート

はじめに

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

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

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

アルゴリズムと言えばソート。選択ソート。

何気に実際のコードに対しては色々とアップデート（DateTime サポートしてみたり、CSV パーサーをサポートしてみたり、ちょこちょこと最適化してみたり）をしているのですが、機能の紹介記事が追い付いていません。軽い話題で場つなぎみたいな感じですが、今回はこれで。

選択ソート

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 selectsort(n, a) {
    var i, j, k, min;

    for (i = 0; i < n - 1; i++) {
        min = a[i];  k = i;
        for (j = i + 1; j < n; j++)
            if (a[j] < min) {  min = a[j];  k = j;  }
        a[k] = a[i];  a[i] = min;
    }
}

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

結果

Before: 99 74  0 62 21 49 37 59  5 43 42 49 73  3 11 86 30 75  1 41
After:   0  1  3  5 11 21 30 37 41 42 43 49 49 59 62 73 74 75 86 99

おわりに

元ソース（C言語）からほとんど修正していない点は合格。そして記載通り単純で実装が簡単。

ではまた、次回。

Kinx アルゴリズム - 選択ソート