新JavaScript例文辞典

配列内のデータをソートする(分布数え/計数ソート)

説明

ソート方法の1つに分布数え/計数ソートがあります。データの値の度数分布を求め累積し、順位に変換し、最後に順位の場所にデータを入れ直すことでソートが行われます。

サンプルプログラム

var data = new Array(30, 10, 5, 99, 44, 65, 10, 31, 1, 57, 89, 78);
function sortData(data,start,end) {
var min = 0; // 最小値
var max = 100; // 最大値
var count = new Array();
var buff = new Array();
for (var i=0; i<=max-min; i++) count[i] = 0;
for (i=0; i<data.length; i++) count[data[i] - min]++;
for (i=1; i<=max-min; i++) count[i] += count[i-1];
for (i=data.length-1; i>=0; i--) {
var n = data[i]-min;
buff[--count[n]] = n;
}
return buff;
}
document.write("ソート前:"+data.toString()+"<br>");
data = sortData(data,0,data.length-1);
document.write("ソート後:"+data.toString()+"<br>");
サンプルを実行
[戻る]