新JavaScript例文辞典

配列内のデータをソートする(基数/ラディックスソート)

説明

ソート方法の1つにラディックスソートがあります。値が整数値で一定の桁数の範囲内である場合に使えます(文字のソートにも使えます)。特定の桁の値に注目し抜き出した値を元に配列に格納していきます。全ての桁数分繰り返すとソートが完了します。

サンプルプログラム

var data = new Array(30,10,5,99,44,65,13,31,1,57,88,78, 120, 94);
function sortData(data){
var buff = new Array();
var count= new Array();
var keta = 3;
for (var i=0; i<10; i++) {
buff[i] = new Array();
count[i]= 0;
}
for (i=0; i<data.length; i++) {
p = data[i] % 10;
buff[p][count[p]++] = data[i];
}
for (var k=1; k<=keta; k++) setData(k);
cnt = 0;
for (var j=0; j<10; j++) for (i=0; i<count[j]; i++) data[cnt++] = buff[j][i];
// ------
function setData(rad) {
var count2 = new Array();
var temp = new Array();
var i,j,p;
for (i=0; i<10; i++) {
temp[i] = new Array();
count2[i]= 0;
}
var div = Math.pow(10,rad); // 10のn乗
for (j=0; j<10; j++) {
for (i=0; i<count[j]; i++) {
p = Math.floor(buff[j][i] / div) % 10;
temp[p][count2[p]++] = buff[j][i];
}
}
buff = temp;
count = count2;
}
}
document.write("ソート前:"+data.toString()+"<br>");
//sortData(data);
sortData(data);
document.write("ソート後:"+data.toString()+"<br>");
サンプルを実行
[戻る]