DouKaku? 6654 syat: JavaScript。クイックソート、か...(比較しないソートの作成)

Comment detail

JavaScript。クイックソート、かな？
効率悪そう。

Array.prototype.sort2 = function(minVal, maxVal) {
    if (this.length <= 1) return this;
    var mid = (minVal + maxVal) / 2;
    var lt = [], eq = [], gt = [];
    for (var i=0; i < this.length; i++) {
        if (this[i] > mid)
            gt.push(this[i]);
        else if (this[i] < mid)
            lt.push(this[i]);
        else
            eq.push(this[i]);
    }
    return lt.sort2(minVal, mid).concat(eq, gt.sort2(mid, maxVal));
};

[-1,9,4,8,9,6,3,9,5,2].sort2(-1,10)

おっと。無駄が多すぎた。
以下の修正で関数に入る回数が109→15に改善しました。

3c3
<       var mid = (minVal + maxVal) / 2;
---
>       var mid = Math.floor((minVal + maxVal) / 2);

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq