配列内のデータをソートする(ビンソート)

説明

ソート方法の1つにビンソートがあります。値の範囲が決まっていて整数値であり値の出現回数が1回である場合のみ利用できます。値の範囲分だけ配列を用意し読み出した値をキーにして対応する配列に格納します。最後に格納したデータだけを連結するとソートが終了します。

サンプルプログラム

var data = new Array(30,10,5,99,44,65,13,31,1,57,88,78);
function sortData(data){
var bin = new Array();
var max = 100; // 最大値(0〜100までの範囲で正の整数で出現数は1回)
for (var i=0; i<max; i++) bin[i] = -1;
for (i=0; i<data.length; i++) bin[data[i]] = data[i];
var count = 0;
for (i=0; i<max; i++) if (bin[i] != -1) data[count++] = bin[i];
}
document.write("ソート前:"+data.toString()+"<br>");
sortData(data);
document.write("ソート後:"+data.toString()+"<br>");
サンプルを実行
[戻る]