比較しないソートの作成 in JavaScript DouKaku?

ソート対象のデータ同士で一切比較などを行わずにソートし、ソート結果を出力するプログラムを作成してください。条件は以下の通り。
・最低値・最大値・個数・並び替え対象の4つを引数として受け取る
・最大値と最低値はあくまで取りうる可能性であり、実際に出現することを保障するものではない。
・同値が複数出現することがある。
・入出力方法及びフォーマットは自由、関数として実装し引数に渡す形でも良い。
・小数点以下の数値が渡されることはないが、負の数は渡される可能性がある。
・最大値や最低値を元に算出した数値との比較は使用しても問題ありません。
・出来るだけ多様な条件のデータをソートできるアルゴリズムを使ってください(データが多少多いときや一定の並び順だとソート失敗するものはダメ)
・昇順降順はどちらでもかまいません

以下サンプル入出力
>>入力
-1 10 10
-1 9 4 8 9 6 3 9 5 2
>>出力
-1 2 3 4 5 6 8 9 9 9

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)

バケツソート。無理矢理感有り。
JScript(WSH)。

-------------------------------
C:\temp>cscript /nologo bucketsort.js
-1 2 3 4 5 6 8 9 9 9

function bucketsort(data,min,max,size){
  var result=[];
  eval( data.replace(/(-?\d+)/g,'result[$1-min]+=",$1,";') );
  return result.join('').split(/[^0-9-]+/).join(' ');
}

WScript.Echo(bucketsort('-1 9 4 8 9 6 3 9 5 2','-1','10','10'));

DouKaku?

比較しないソートの作成

Posted feedbacks - JavaScript

Index

Feed

Other

Link

Pathtraq