Non-Comparison Sorting

Non-comparison Sort

• 사전지식을 활용해 정렬

counting sort

• k 이하의 정수 정렬
• dictionary처럼해서 i가 몇번나왔나 센다
• stable algorithm

radix sort

• 예를 들어, k 자리 수의 정수들을 정렬하는 경우, 각 자리 수마다 counting sort를 해준다
• 가능한 이유 : counting sort가 stable algorithm이기 때문이다. 

//3자리 정수 radix sort
var test =Array.from({length: 20}, () => Math.ceil(Math.random() * 899)+100);
test=test.map(function(e){return String(e).split('').map(function(a){return Number(a)})})

function counting(array,idx)
{
var n = 9
for(var i=0;i<=n;i++)
{
    counting[i]=0
}

for(var i=0;i<array.length;i++)
{
    counting[array[i][idx]]++;
}

var prev =0;
for(var i=0;i<=n;i++)
{
    if(counting[i]>0)
    {
        counting[i] = counting[i] + prev
        prev = counting[i]
    }
}
var result = Array(array.length).fill('')


for(var i=array.length-1;i>=0;i--)
{
    var j = counting[array[i][idx]]
    result[j-1] = array[i]
    counting[array[i][idx]]--;
}

return result
}

console.log(test)
for(var j=2;j>=0;j--)
{
    test = counting(test,j)
    console.log(test.map(function(e){return Number(e.join(''))}))
}