정렬 - 기수정렬

기수 정렬

• 자릿수를 기준으로 차례대로 데이터를 정렬하는 알고리즘
  • 1의 자리수를 기준으로 오름차순으로 정렬
  • 그 데이터를 다시 10의 자리수를 기준으로 오름차순으로 정렬
  • ... 반복
• 정렬하는 법
  • bucket[10] 에 자리수 별로 count 함. 19이면 bucket[9]++ 이런 식.
  • 이 버켓을 누적함. bucket[i + 1] = bucket[i] + bucket[i + 1]
  • 뒷 숫자부터 버켓에 담긴 인덱스 대로 집어 넣음. 맨 뒷 숫자가 37이고, bucket[7]이 3이라면 세번째 배열(result[2])에 넣는 것.
  • 결과물 배열을 다시 원 배열에 복사
  • 이 과정을 반복
• 가장 큰 자릿수를 D라고 했을 때 O(DN)의 시간 복잡도

#define MAX 10000

void    radixSort(int *a, int n)
{
    int res[MAX];
    int    max_value = 0;
    int    jaritsu = 1;

    for (int i = 0; i < n; i++)
    {
        if (a[i] > max_value)
            max_value = a[i];
    }
    while (max_value / jaritsu > 0)
    {
        for (int i = 0; i < n; i++)
            bucket[a[i] / jaritsu % 10]++;
        for (int i = 0; i < 9; i++)
            bucket[i + 1] = bucket[i] + bucket[i + 1];
        for (int i = n - 1; i >=0 ; i--)
            res[--bucket[a[i] / jaritsu % 10]] = a[i];
        for (int i = 0; i < n; i++)
            a[i] = res[i];
        jaritsu *= 10;
    }
}