データが取り得る値の範囲が分かっている場合、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)である