0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

Kinx アルゴリズム - クイックソート

Last updated at Posted at 2020-04-27

アルゴリズム - クイックソート

はじめに

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

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

アルゴリズムと言えばソート。その中でも一番使うであろうクイックソートです。

クイックソート

サンプル

テスト・ドライバ

以下のコードを共通のテスト・ドライバコードとして使います。

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.hqsort を使うように最適化されています。

...ということは、もしかすると 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

...やはり。ではでは、また次回。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?