[Algorithm] 기수 정렬 계수 정렬 Node.js

문제

 

정수를 요소로 가지는 배열을 입력받아 오름차순으로 정렬된 값을 반환해야 합니다. 

 

입/출력

 

입력값 arr

• Number 타입 요소를 가진 배열
• arr[i] >= 0
• arr.length <= 10,000
• 중첩되지 않은 1차원 배열입니다.

 

출력값 

• Number 타입 요소를 가진 배열
• 배열의 요소는 오름차순으로 정렬되어야 합니다.
• arr[i] <= arr[j] (i < j)

 

 

 

주의사항

 

기수 정렬(Radix Sort)를 구현해야 합니다. 따라서 arr.sort() 메소드 사용은 금지됩니다. 

 

풀이

 

기수 정렬은 기수 별로 비교를 진행하지 않고 정렬하는 알고리즘입니다. 기수에 따라 요소를 버킷에 집어넣기 때문에 비교 연산이 필요없습니다. 기수 정렬 시간복잡도는 O(nw)입니다. w는 기수의 크기를 의미합니다. 버킷 정렬 일부로 취급되기도 합니다. 

기수 정렬이 탄생한 배경을 보면 1887년 허먼 홀러리스가 작표기를 만든 시점에 고안됩니다. 기수 정렬 알고리즘은 1923년 천공 카드를 분류하는 방법으로 사용되기도 하였습니다. 기수 정렬은 기수 테이블 만큼의 추가 메모리가 필요하지만 비교 연산이 필요없는 정수나 문자열 비교시 50% 에서 3배 가까이 시간복잡도를 낮출 수 있는 알고리즘입니다. 

기수 정렬이란?

 

기수 정렬을 수행하는 방법은 각 자리수에 해당하는 숫자로 기수 테이블에 채워 넣고, 기수를 늘려가는 방식으로 정렬을 수행합니다. 예를 들어 const=[170,45,75,90,2,24,802,66] 배열이 주어지면 먼저 1의 자리부터 정렬합니다.

 

 

1의 자리를 정렬했을 때 정렬 결과는 다음과 같습니다.

[170, 90, 2, 802, 24, 45, 75, 66]

 

다음으로 10 자리에 대해 정렬을 진행합니다.

[2, 802, 24, 45, 66, 170, 75, 90]

마지막으로 100 자리에 대해 정렬을 진행합니다.

[2, 24, 45, 66, 75, 90, 170, 802]

 

기수 정렬을 구현하기 위해서 max 값을 구해야 합니다. 가장 큰 값의 자리 수만큼 정렬 과정이 반복되어야 합니다.

const getMax = (arr) =>{
    return arr.reduce((max, item)=>{
        if(item > max) return item;
        return max;
    }, 0);
}

 

기수 정렬 내부적으로는 계수 정렬(Counting Sort)를 돌립니다. 기수 테이블 만큼의 새로운 테이블을 생성하고, count의 누적개수를 갱신하여 전체 배열을 반대로 순회하면서 특정 기수에서 정렬을 진행합니다.

const countingSort = (arr, radix) => {
    const N = arr.length;
    const output = Array(N).fill(0);
    const count = Array(10).fill(0);

    // 현재 자리수 기준으로 0~9 자리수 개수를 카운팅 한다.
    arr.forEach((item)=>{
        const idx = Math.floor(item / radix) % 10;
        count[idx]++;
    })


    // count[i]가 i 까지의 누적 개수가 되도록 한다.
    count.reduce((totalNum, num, idx)=>{
        count[idx] = totalNum + num;
        return totalNum + num;
    }, 0);



    // 배열을 거꾸로 순회한다.
    let i = N - 1; 
    while(i >= 0){
        const idx = Math.floor(arr[i] / radix) % 10; 
        output[count[idx] - 1] = arr[i]; 
        count[idx] -= 1;
        i--;
    }
    return output;

}

 

정수가 음수 영역까지 확장되는 경우 음수와 양수를 구분해서 계수 정렬 + 기수 정렬을 수행합니다.

/* 정수의 범위 확장 */

    // 주어진 배열을 양수와 음수의 영역으로 구분
    // 음수는 절대값으로 변경한다.
    // 음수는 다시 음수로 바꿔 기수 정렬 진행
    let left = [];
    let right = [];
    let max = 0;
    let radix = 0;


    arr.forEach((item)=>{
        if(item >= 0) right.push(item);
        else left.push(item * - 1);
    })

    max = getMax(left);
    radix = 1;
    while(parseInt(max / radix) > 0){
        left = countingSort(left, radix);
        radix *= 10;
    }

    max = getMax(right);
    radix = 1;
    while(parseInt(max / radix) > 0){
        right = countingSort(right, radix);
        radix *= 10;
    }

    return left.reverse().map(item=>item*(-1)).concat(right);

 

 

 

 

기수정렬 Node.js 구현

function radixSort(arr) {
    // todo: 여기에 코드를 작성합니다.

	const getMax = (arr) =>{
        return arr.reduce((max, item)=>{
            if(item > max) return item;
            return max;
        }, 0);
    }

    const countingSort = (arr, radix) => {
        const N = arr.length;
        const output = Array(N).fill(0);
        const count = Array(10).fill(0);

        // 현재 자리수 기준으로 0~9 자리수 개수를 카운팅 한다.
        arr.forEach((item)=>{
            const idx = Math.floor(item / radix) % 10;
            count[idx]++;
        })


        // count[i]가 i 까지의 누적 개수가 되도록 한다.
        count.reduce((totalNum, num, idx)=>{
            count[idx] = totalNum + num;
            return totalNum + num;
        }, 0);



        // 배열을 거꾸로 순회한다.
        let i = N - 1; 
        while(i >= 0){
            const idx = Math.floor(arr[i] / radix) % 10; 
            output[count[idx] - 1] = arr[i]; 
            count[idx] -= 1;
            i--;
        }
        return output;

    }

    /* 양의 정수인 경우 */
    /* 
        const max = getMax(arr);
        let radix = 1;
        while(parseInt(max / radix) > 0){
            arr = countingSort(arr, radix);
            radix *= 10;
        }

        return arr;
    */

    /* 정수의 범위 확장 */

    // 주어진 배열을 양수와 음수의 영역으로 구분
    // 음수는 절대값으로 변경한다.
    // 음수는 다시 음수로 바꿔 기수 정렬 진행
    let left = [];
    let right = [];
    let max = 0;
    let radix = 0;


    arr.forEach((item)=>{
        if(item >= 0) right.push(item);
        else left.push(item * - 1);
    })

    max = getMax(left);
    radix = 1;
    while(parseInt(max / radix) > 0){
        left = countingSort(left, radix);
        radix *= 10;
    }

    max = getMax(right);
    radix = 1;
    while(parseInt(max / radix) > 0){
        right = countingSort(right, radix);
        radix *= 10;
    }

    return left.reverse().map(item=>item*(-1)).concat(right);
}

console.log(radixSort([21,3,1,-11,13,101,600,-222]))

 

 

[Algorithm] 최단거리 알고리즘 문제 Node.js

 

[Blockchain] 블룸 필터(Bloom Filter)란?

 

[Algorithm] 두 배열에서 k 번째 수 찾기 Javascript(getItemFromTwoSortedArrays 알고리즘)

 

[Algorithm] BFS Queue 자바스크립트(primePassword 문제) 구현