정렬 - 기수정렬

기수 정렬

기수 정렬은 값의 자릿수를 이용해서 정렬하는 특이한 정렬인데,

이는 비교를 하지 않고 정렬한다는 또 다른 특징을 가지고 있다.

우선 n진수인지에 따라서 n개의 저장 공간 (일반적으로 스택 등) 을 마련한다.

배열과는 다르게, 이 저장 공간에는 여러 데이터가 들어갔다가 순차적으로 나올 수 있어야 한다.

그리고 나서, n진수의 끝의 자리 숫자 (10진수라면 1의 자리 숫자) 를 기준으로, 해당 값에 맞는 버킷을 값을 push 한다.

예를 들어, 142 라는 값은 2 번째 버킷에 들어가는 형식이다.

이후, 이 모든 버킷들을 첫번재 버킷부터 순차적으로 pop 하면서 배열에 다시 담는다.

그 후, 배열의 값 중 최대 자리 수만큼 이 행위를 반복하면서, 정렬을 만들어내는 과정이다.

generateRandomArray, printArray, swap

static int arrayLength = 20;
int *myArray = generateRandomArray(arrayLength); // 랜덤 값을 가진 배열 생성

printArray(myArray, arrayLength); // 정렬 전 배열 출력

queue<int> myQueue[10]; // 기수정렬을 위한 n진수만큼의 큐 버킷 생성

int radix = 1; // 최대 자리수
int maxValue = myArray[0]; // 배열의 최대 값 찾기
for (int i = 0; i < arrayLength; i ++) {
    if (maxValue < myArray[i]) maxValue = myArray[i];
}
while (true) { // 최대 자리 수 찾기
    if (radix >= maxValue) break;
    radix *= 10;
}

for (int currentRadix = 1; currentRadix < radix; currentRadix *= 10) { // 일의자리부터 최대자리수까지 루프
    for (int i = 0; i < arrayLength; i ++) { // 배열을 순회한다
        myQueue[myArray[i] / currentRadix % 10].push(myArray[i]); // 해당 자리수의 끝자리에 맞는 버킷으로 push
    }

    int arrayIndex = 0; // 배열 인덱스
    for (int j = 0; j < 10; j ++) { // 버킷을 순회한다
        while (myQueue[j].empty() == false) { // 버킷에 값이 존재하면
            myArray[arrayIndex] = myQueue[j].front(); // 배열의 인덱스에 버킷의 맨 첫 값 추가 
            myQueue[j].pop();
            arrayIndex++; // 배열 인덱스 증가
        }
    }
}

printArray(myArray, arrayLength); // 정렬 후 배열 출력

작은 것부터, 점점 커지게, 오름차순으로 정렬한 예제이다.

이러한 기수 정렬은 O(N) 의 복잡도를 가지게 된다. O(N) 이 여러 단계에 걸쳐 존재하므로, 합연산에 의해 계산된다.

하지만 이러한 기수 정렬은, 다른 정렬에 비해 메모리를 추가로 요구하게 되므로 장단점이 있다 할 수 있다.