[Sorting] 5. Non-Comparison Sorting - Counting Sort, Radix Sort

non - Comparisons Sorting Algorithm

Counting Sort

Space Complexity : in-place 알고리즘이 아니다. buffer를 필요로 한다.

Time Complexity : O(n + k)

Radix Sort에 대해 알아보기 전에 Count Sort에 대해서 먼저 알아보자. Count Sort에서 사용된 알고리즘이 Radix Sort에서 사용된다. 즉 Radix Sort는 Count Sort의 확장판이라고 할 수 있다.

Count Sort는 말 그대로 몇 개인지 개수를 세어 정렬하는 방식이다. 정렬하고자 하는 값 중 최대값에 해당하는 값을 size로 하는 임시 배열을 만든다. 만들어진 배열의 index 중 일부는 정렬하고자 하는 값들이 되므로 그 값에는 그 값들의 개수를 나타낸다. 정렬하고자 하는 값들이 몇 개씩인지 파악하는 임시 배열이 만들어졌다면 이 임시 배열을 기준으로 정렬을 한다. 그 전에 임시 배열에서 한 가지 작업을 추가적으로 수행해주어야 하는데 큰 값부터 즉 큰 index 부터 시작하여 누적된 값으로 변경해주는 것이다. 이 누적된 값은 정렬하고자 하는 값들이 정렬될 index 값을 나타내게 된다. 작업을 마친 임시 배열의 index는 정렬하고자 하는 값을 나타내고 value는 정렬하고자 하는 값들이 정렬되었을 때의 index를 나타내게 된다. 이를 기준으로 정렬을 해준다.

c code>

//Counting sort!!
void counting_sort(int * arr, int size, int maxValue) {
    if(arr == NULL) return;
    int bufferArr[maxValue];
    int resultArr[size];
    //bufferArr initialize
    memset(bufferArr, 0, (maxValue + 1) * sizeof(int));
    //index 값에 해당하는 원소들을 버퍼에서 세어준다.
    for(int i = 0; i < size; i++) {
        bufferArr[arr[i]]++;
    }
    //누적해서 세면서 buffer 배열 값을 채워나간다.
    for(int i = 1; i < maxValue + 1; i++) {
        bufferArr[i] += bufferArr[i-1];
    }
    //bufferArr을 기준으로 resultArr에 input에 대한 값을 정렬해준다.
    for(int i = size - 1; i >= 0; i--) {
        resultArr[bufferArr[ (arr[i])] - 1 ] = arr[i];
        bufferArr[arr[i]]--;
    }
    //resultArr 값을 기존의 배열로 바꿔준다.
    for(int i = 0; i < size; i++) {
        arr[i] = resultArr[i];
    }
}

Radix Sort

정렬 알고리즘의 한계는 O(n log n)이지만, 기수 정렬은 이 한계를 넘어설 수 있는 알고리즘이다. 단, 한 가지 단점이 존재하는데 적용할 수 있는 범위가 제한적이라는 것이다. 이 범위는 데이터 길이에 의존하게 된다. 정렬하고자 하는 데이터의 길이가 동일하지 않은 데이터에 대해서는 정렬이 불가능하다. 숫자말고 문자열의 경우도 마찬가지이다. ( 불가능하다는 것은 기존의 정렬 알고리즘에 비해 기수 정렬 알고리즘으로는 좋은 성능을 내는데 불가능하다는 것이다. )

기수(radix)란 주어진 데이터를 구성하는 기본요소를 의미한다. 이 기수를 이용해서 정렬을 진행한다. 하나의 기수마다 하나의 버킷을 생성하여, 분류를 한 뒤에, 버킷 안에서 또 정렬을 하는 방식이다.

기수 정렬은 LSD(Least Significant Digit) 방식과 MSD(Most Significant Digit) 방식 두 가지로 나뉜다. LSD는 덜 중요한 숫자부터 정렬하는 방식으로 예를 들어 숫자를 정렬한다고 했을 때, 일의 자리부터 정렬하는 방식이다. MSD는 중요한 숫자부터 정렬하는 방식으로 세 자리 숫자면 백의 자리부터 정렬하는 방식이다.

두 가지 방식의 Big-O는 동일하다. 하지만 주로 기수정렬을 이야기할 때는 LSD를 이야기한다. LSD는 중간에 정렬 결과를 볼 수 없다. 무조건 일의 자리부터 시작해서 백의 자리까지 모두 정렬이 끝나야 결과를 확인할 수 있고, 그 때서야 결과가 나온다. 하지만 MSD 는 정렬 중간에 정렬이 될 수 있다. 그러므로 정렬하는데 걸리는 시간을 줄일 수 있다. 하지만 정렬이 완료됬는지 확인하는 과정이 필요하고 이 때문에 메모리를 더 사용하게 된다. 또 상황마다 일관적인 정렬 알고리즘을 사용하여 정렬하는데 적용할 수 없으므로 불편하다. 이러한 이유들로 기수 정렬을 논할 때는 주로 LSD에 대해서 논한다.

5. the end