[알고리즘] 정렬(3) - 기수 정렬, 카운팅 정렬

반응형

 

\(\Theta(n^2)\)와 \(\Theta(nlogn)\)이 소요되는 정렬 알고리즘들을 알아봤다. 이번에는 특수한 상황에서 사용할 수 있는 알고리즘을 살펴보겠다.

기수 정렬(Radix Sort)

기수 정렬이란 입력이 모두 k 자릿수 이하의 자연수인 경우에 사용할 수 있는 알고리즘이다. 가장 낮은 자릿수만으로 수를 정렬한 뒤, 다음 자릿수로 정렬, ... 를 반복해서 정렬된 배열을 얻는 방법이다. 이때, 같은 수라면 먼저 들어간 수가 위로 정렬된다.

C++로 구현한 기수 정렬

const int PLACE_VALUE = 10;
const int DIGIT = 2;

void radix_sort(int* arr, int start, int end) {
    std::queue<int> k[PLACE_VALUE]; // 자릿값 0 ~ 9
    int d = 1;

    for (int i = 0; i < DIGIT; i++) {
        for (int j = start; j <= end; j++) {
            k[(arr[j] / d) % 10].push(arr[j]); // 수를 자릿값에 해당되는 번호의 큐로 삽입
        }

        for (int j = 0, idx = 0; j < PLACE_VALUE; j++) {
            while (!k[j].empty()) {
                arr[idx] = k[j].front();
                k[j].pop();
                idx++;
            }
        }
        
        d *= 10;
    }
}

기수 정렬의 경우에는 항상 \(O(kn)\)의 시간 복잡도를 가진다. 여기서 \(k\)는 자릿수 DIGIT이다. 첫 번째 for문이 DIGIT 만큼 반복되고, 두 번째 for문은 \(n\)번만 반복될 것이다. 그렇다면 \(k\)가 \(n\)과 같아지면 \(O(n^2)\) 일 수도 있지 않겠나 생각이 들겠지만, 당장 32비트 정수의 자릿수는 최대 10자리, 64비트 정수는 최대 19자리이다. \(k\)의 값이 아무리 커봐야 충분히 큰 \(n\)에 비하면은 아주 작은 수가 된다.

카운팅 정렬(Counting Sort)

카운팅 정렬은 배열의 원소들이 1부터 k까지의 자연수가 각각 몇 번 나타나는지를 센 후, 이를 통해 배열을 정렬하는 알고리즘이다. 항상 원소들은 k의 값 보다 커서는 안 된다.

1. arr = [ 6, 2, 9, 7, 3, 10, 4, 1, 8, 5 ] 가 있고, k는 10이라고 한다.
2. k + 1 만큼 크기의 count 배열을 선언한다.
count = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
3. arr의 각 원소를 i라고 할때, count[i]의 위치에 1을 더해준다.
count = [ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
4. count[i]가 i보다 작거나 같은 원소의 총 수를 가지도록 한다. (0 ≤ i ≤ k)
count[i] += count[i - 1]
count = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
5. 정렬된 원소를 담을 배열을 만들어 준다.
srt_arr[k] = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
6. count[arr[0]] - 1의 값을 j라고 하면, srt_arr[j]에 arr[0]의 값을 넣는다.
arr[0] = 6, count[6] = 6, j = 5
srt_arr = [ 0, 0, 0, 0, 0, 6, 0, 0, 0, 0 ]
7. 6의 과정을 반복해서 정렬된 배열을 얻는다.
arr = srt_arr

void counting_sort(int* arr) {
    int k = 0;
    
    for (int i = 0; i < SIZE; i++) {
        k = std::max(k, arr[i]);
    }

    std::vector<int> count(k + 1, 0);
    std::vector<int> srt_arr(SIZE, 0);

    for (int i = 0; i < SIZE; ++i) {
        count[arr[i]] += 1;
    }

    for (int i = 1; i < SIZE + 1; ++i) {
        count[i] += count[i - 1];
    }

    for (int i = 0; i < SIZE; ++i) {
        srt_arr[count[arr[i]] - 1] = arr[i];
    }

    for (int i = 0; i < SIZE; ++i) {
        arr[i] = srt_arr[i];
    }
}

시간 복잡도가 \(O(n)\)이 된다는 것은 이제 코드만 봐도 알 수 있다. 하지만 이는 k가 \(O(n)\)을 넘지 않는, 즉, 배열의 원소들이 k를 넘지 않은 경우에만 가능하다. 이를 초과하게 된다면 다른 정렬을 이용하는 편이 낫다.

 

 

[Reference]

문병로, 「쉽게 배우는 알고리즘」 (한빛 아카데미, 2018)

 

 

728x90