アルゴリズム - バブルソート
はじめに
「見た目は JavaScript、頭脳(中身)は Ruby、(安定感は AC/DC)」 でお届けしているスクリプト言語 Kinx。「プログラム=アルゴリズム+データ構造」。アルゴリズムの実装例をご紹介。
元ネタは「C言語による(30年経っても)最新アルゴリズム事典」。今回はソート(バブルソート)です。
- 参考
- 最初の動機 ... スクリプト言語 KINX(ご紹介)
- 個別記事へのリンクは全てここに集約してあります。
- リポジトリ ... https://github.com/Kray-G/kinx
- Pull Request 等お待ちしております。
- 最初の動機 ... スクリプト言語 KINX(ご紹介)
アルゴリズムと言えばソート。今回はバブルソートです。
バブルソート
-
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言語)のコードからほとんど修正せずに使えています。素晴らしい。
ではまた、次回。