10. 기수 정렬 - 기수정렬 특징 / 기수 정렬의 원리 / 기수정렬 구현하기

기수정렬

 기수정렬(Radix Sort)는 자릿수를 기준으로 차례대로 데이터를 정렬하는 알고리즘이다. 각 데이터를 자릿수를 기준으로 분류하므로 가장 큰 자릿수를 D라고 했을 때 O(DN)의 시간 복잡도를 가진다. 그런데, 자릿수가 10개를 넘어가야 억단위가 넘어가기 때문에, 왠만해선 D는 그렇게 큰 값이 아닐 경우가 많다. 따라서 O(DN)은 사실상 O(N)의 시간복잡도를 가진다고 볼 수 있을 정도이므로, 계수 정렬만큼 처리속도가 빠르다. 계수 정렬보다 약간 더 느릴 순 있으나, 숫자가 매우 큰 상황에서도 사용할 수 있으므로, 계수정렬보다 활용할 수 있는 상황이 더 다양하다.

 

기수정렬의 원리

다음과 같은 원소 배열이 있을때, 기수 정렬은 다음과 같이 수행된다.

먼저 정렬할 배열의 '원소의 1의 자리를 기준'으로, 자릿수 배열의 인덱스에 해당하는 원소가 있을 때 마다 +1씩 추가한다. 단, 인덱스에 원소를 추가할 땐 누적값에 +1씩 추가된다. 결과 배열을 만들 땐, 정렬할 배열의 가장 뒤의 원소부터 자리를 선정한다. 자리를 넣어준 숫자에 해당했던 자릿수 배열의 원소는 -1씩 더한다.

정렬할 배열의 가장 뒷 원소부터 결과배열의 자리를 채운다. 1의 자리까지 정렬 완료된 모습.

위의 과정을, 정렬할 배열의 원소중 가장 큰수의 자릿수까지 진행하면, 결과배열이 오름차순으로 정렬되는것을 볼 수 있는데, 그 과정은 다음과 같다. 다음 자릿수를 정렬할 땐, 이전 자릿수의 결과배열을 가지고 정렬한다.

 

오름차순으로 정렬 완료된 모습

 

기수 정렬 구현하기

위에서 본 기수정렬을 C언어로 구현해보면 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX 10000 //원소 만개까지 정렬 가능

void radixSort(int *a. int n) {
    int res[MAX], maxValue = 0; // 결과배열, 자릿수 결정할 최댓 값
    int exp =1; //exp 변수가 *10씩 증가하면서 1의 자리부터 쭉 계산될 수 있게 할 것임
    for(int i = 0; i < n; i++){
        if(a[i] > maxValue) maxValue = a[i]; //가장 큰값 찾기
    }
    while (maxValue / exp > 0){
        int bucket[10] = {o}; //자릿수 배열 초기화(자릿수가 바뀔 때 마다)
        for (int i = 0; i < n; i++) bucket[a[i] / exp % 10]++; //자릿수 배열 처리(현재 보고있는 자릿수에 해당하는 값에 카운트 +1
        for (int i = 0; i < 10; i++) bucket[i] += bucket[i-1]; //자릿수 배열 -> 누적 계산
        for (int i = n-1; i>=0; i--){ //배열의 가장 뒤의 원소부터 정렬 
            res[--bucket[a[i]/ exp % 10]] = a[i]
        }
        for(int i =0; i < n; i++) a[i] = res[i]; //기본 배열 갱신
        exp *= 10; //다음 자릿수로 이동하기 위해
    }
}

int main(void){ //기수 정렬 메인함수에서 사용하기
    int a[MAX];
    int i, n;
    scanf("%d", &a[i]);
    for(i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    radixSort(a, n);
    for ( i = 0; i < n; i++){
        printf("%d", a[i]);
    }
    system("pause");
}