계수 정렬 구현해보기

원소끼리 비교 하지 않고 정렬을 하는 알고리즘이다.

원소를 하나하나 비교를 하지 않고 각 숫자가 몇개인지 세어 숫자에 해당하는 배열 인덱스에 저장하여 정렬한다.

이때 배열 인덱스에 저장하여 정렬하는 방식이므로 정렬할 값이 정수일 때 사용 가능하다.

방법

1. 0부터 가장 큰 원소까지의 범위가 모두 담길 수 있는 배열을 생성한다.
2. 원소 값과 동일한 인덱스의 배열 값을 1씩 증가한다.
3. 배열을 순회하여 0인 값을 제외하고 해당 값만큼 인덱스를 출력한다.

시간 복잡도

원소들을 순회하며 count하는 과정에서 O(N)이 소요된다.

이때, 원소의 최댓값 K가 굉장히 클 경우 정렬 시간의 변수로 작용한다.

(계수 정렬에서 정렬된 값을 출력할 때 1번 인덱스 ~ 원소의 최댓값인 K번 인덱스까지 모두 순회해야 하기 때문)

⇒ 계수 정렬의 시간복잡도는 O(N+K)

장점

원소의 최대 최소 범위가 작을 때는 O(n)의 시간 복잡도를 가진다.
즉, 원소는 매우 많으나 최대 최소 범위가 작을 경우 적합하다.
중복된 원소의 순서가 정렬 후에도 유지되므로 stable 정렬이다.

단점

데이터의 범위가 크면 만들어야 하는 배열의 크기가 커지므로 공간 복잡도가 커진다. ⇒ 메모리 낭비가 커진다.

counting을 하기 위한 추가적인 배열이 필요하다. 따라서 in-place sort가 아니며 배열 내에서 교환하지 않는다.

class CountingSort {
    sort(data){

        const max = Math.max(...data);
        const countArr = Array.from({length: max + 1}, () => 0); // max + 1 크기의 array 생성

        let len = data.length;
        for (let i = 0; i < len; i++) {
            countArr[data[i]]++;
        }

        // countArr의 값이 1이상일 때
        // 해당 인덱스 값을 data에 넣어주면 정렬이 완료
        let idx = 0;
        len = countArr.length;
        for (let i = 0; i < len; i++) {
            if (countArr[i] > 0) {
                for (let j = 0; j < countArr[i]; j++) {
                    data[idx++] = i;
                }
            }
        }
        return data;
    }
}