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