@blog.justoneplanet.info

データが取り得る値の範囲が分かっている場合、O(n log n)の限界を超えて、O(n)の計算量でソートできる。

■実装

var a = [5, 7, 3, 9, 1, 4, 6, 8, 2, 0];
array = a.concat();

/**
 * countingSort
 * @param {array} ary
 * @param {int} max
 */
var countingSort = function(ary, max){
    var bucket = [];
    for(var i = 0; i <= max; i++){
        bucket.push(0);
    }// バケツの準備
    for(var i = 0; i < ary.length; i++){
        bucket[ary[i]]++;
    }// i番目の要素に与えられた配列の要素値iの出現回数が記録される

    var store = 0;
    for(var i = 0; i <= max; i++){
        while(bucket[i]-- > 0){
            ary[store++] = i;
        }
    }// 出現回数に応じて元の配列を上書きする
}

countingSort(a, 9);
console.log("before : " + array.toString());
console.log("after  : " + a.toString());
//before : 5,7,3,9,1,4,6,8,2,0
//after  : 0,1,2,3,4,5,6,7,8,9

■特性

• 要素の値に重複があっても良い
• 要素の値が取り得る最大値が分からなくてはならない
• 計算量はO(n)である