카운팅 정렬

카운팅 정렬은 도수 정렬, 계수 정렬 등 다양한 이름으로 불리우는 방식입니다. 책마다, 사람마다 다른 이름을 사용하고 있지만 모두 같은 정렬을 말하고 있으며 이 블로그에서는 카운팅 정렬이라고 부를 예정입니다.

---

1. 카운팅 정렬

카운팅 정렬은 정렬 시 대소 관계를 판단하지 않고 정렬하는 정렬법입니다. 카운팅 정렬을 시간복잡도가 O(n)으로 빠른 알고리즘이지만, 정렬하려는 대상에 따라서 시간 복잡도가 매우 커질 수 있습니다. 정확히는 시간 복잡도가 O(n+k)이기 때문입니다. 여기서 k는 컬렉션 내부의 최대 숫자입니다. 그래서 k가 무지막지하게 커질 경우 시간도 오래걸리게 됩니다. 이렇게 되는 이유는 잠시 후 카운팅 정렬의 방식을 공부해보면 알 수 있습니다.

그리고 그동안 배운 몇 가지의 정렬법이 모두 두 요소를 비교 하고 대소 관계에 따라 삽입하거나 추가했다면, 카운팅 정렬은 비교가 없는 정렬입니다.

 

 

2. 카운팅 정렬의 작동 원리

이번에 쓰일 컬렉션은 지금까지 봤던 배열들과 조금은 다른 형태입니다. 시험을 보고난 후 학생들의 성적 집합이라고 생각하면 편할 것 같습니다. 다음과 같은 배열을 정렬하려고 합니다.

첫 번째로 할 일은 각 배열의 요소가 몇 번 등장하는지(도수분포표)를 위한 배열을 만들어 줍니다. 위의 배열에서는 1부터 4까지니까 길이가 4인 배열을 만들고 0으로 초기화 해줍니다. 이 배열이 요소를 카운트하기때문에 카운팅 정렬이라는 이름이 붙게 된 것 입니다.

카운트용 배열

카운팅 배열을 만들었으니 이제 배열은 한바퀴 돌면서 각 요소의 갯수를 세어줍니다.

카운팅한 각 요소를 누적합으로 만들어줍니다.

이제 구한 누적합을 가지고 정렬을 해주면 됩니다. 1은 2, 2는 5, 3은 6, 4는 8에 순서대로 넣으면 1이 두번 나오고 2가 세번나오고...하는 식으로 정렬이 완료됩니다.

이렇게 보니 굉장히 간편하고 좋은 것 같지만 이것은 예시가 1~4까지의 작은 범위라 그렇고 만약 1~100까지라면, 1~10000까지라면? 배열을 10000개 크기로 선언해 주어야하고 그것들을 세어야하기 때문에 메모리 낭비와 시간 소모가 발생하게 됩니다. 따라서 카운팅 배열은 컬렉션 내부의 요소가 적당한 범위를 갖고 있고 확실하게 분포를 알 수 있는 경우에 사용해야 가장 효율적인 알고리즘이라고 할 수 있습니다.

 

 

3. 카운팅 정렬 구현

위의 방식을 토대로 카운팅 정렬을 구현해보도록 하겠습니다. 여기서는 프로그래머가 최댓값을 알고있다는 가정 하에서 인수로 넘겨 인자로 사용합니다. 실제로 사용에서는 max인 k를 구하는 과정을 따로 거친다음 인수로 넘기는 방식이 안정적이고 좋은 프로그래밍입니다.

export const countingSort = (arr, k) => {
    //카운팅을 할 배열
    let counter = Array.from({length: k + 1}, () => 0);
    //정렬할 결과를 저장할 배열
    let result = Array.from({length: arr.length}, () => 0);
    let i;
    
    //각 요소의 수를 카운팅
    for (i = 0; i < arr.length; i++) {
        counter[arr[i]]++;
    }

    //카운팅 배열을 누적합으로 만들기
    for (i = 1; i <= k; i++) {
        counter[i] += counter[i - 1];
    }

    //누적합을 기준으로 만들었던 배열을 결과 배열에 정렬하기
    for (i = arr.length - 1; i >= 0; i--) {
        result[--counter[arr[i]]] = arr[i];
    }

    return result;
};

import {countingSort} from './study-code/sort/counting-sort.js';

let arr = [3, 2, 2, 4, 1, 2, 4, 1];

console.log(countingSort(arr, 4));

---

https://github.com/Bam-j/algorithm-study/blob/main/study-code/sort/counting-sort.js

GitHub - Bam-j/algorithm-study: 블로그 알고리즘 정리 포스트 코드 수록 + 코딩 테스트 코드 수록