기수정렬(Radix Sort)

기수정렬은 데이터를 자릿수 기준으로 나누어서 정렬을 수행합니다. 예를 들어, 10진수의 경우 각 자릿수는 0부터 9까지의 숫자 중 하나입니다. 따라서, 10진수 데이터를 기수정렬할 때는 0부터 9까지의 숫자를 각 자릿수로 사용하여 정렬을 수행합니다.

기수정렬의 구체적인 과정은 다음과 같습니다.

1. 가장 작은 자릿수부터 가장 큰 자릿수까지 반복적으로 정렬을 수행합니다.
2. 각 자릿수별로 데이터를 정렬하기 위해, 해당 자릿수의 값에 따라 버킷에 데이터를 넣습니다.
3. 버킷에 있는 데이터를 순서대로 꺼내서 다시 배열에 넣습니다. 이때, 버킷에 들어있는 데이터의 순서는 유지됩니다.
4. 가장 큰 자릿수까지 반복하면, 정렬이 완료됩니다.

기수정렬은 안정적인 정렬 알고리즘이며, 데이터의 크기와 무관하게 일정한 시간복잡도 O(d * (n+k))를 가집니다. 여기서 d는 자릿수, n은 데이터의 개수, k는 데이터의 값의 범위입니다. 따라서, 데이터의 크기가 작을 때는 다른 정렬 알고리즘보다 느릴 수 있지만, 데이터의 크기가 매우 클 경우에는 기수정렬이 다른 정렬 알고리즘보다 효율적입니다.

#include <stdio.h>
#include <stdlib.h>

// 배열 a[]의 최댓값을 반환하는 함수
int getMax(int a[], int n) {
    int max = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] > max) {
            max = a[i];
        }
    }
    return max;
}

// 기수정렬 함수
void radixSort(int a[], int n) {
    int max = getMax(a, n);
    int exp = 1;
    int *tmp = (int *)malloc(n * sizeof(int));

    while (max / exp > 0) {
        int bucket[10] = {0};

        // 각 자리수별로 버킷에 데이터를 넣습니다.
        for (int i = 0; i < n; i++) {
            bucket[(a[i] / exp) % 10]++;
        }

        // 누적합을 구합니다.
        for (int i = 1; i < 10; i++) {
            bucket[i] += bucket[i - 1];
        }

        // 버킷에 있는 데이터를 순서대로 tmp 배열에 넣습니다.
        for (int i = n - 1; i >= 0; i--) {
            tmp[--bucket[(a[i] / exp) % 10]] = a[i];
        }

        // tmp 배열의 데이터를 a 배열에 복사합니다.
        for (int i = 0; i < n; i++) {
            a[i] = tmp[i];
        }

        // 다음 자릿수로 이동합니다.
        exp *= 10;
    }

    // 메모리를 해제합니다.
    free(tmp);
}

// 배열 출력 함수
void printArray(int a[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

// 메인 함수
int main() {
    int a[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(a) / sizeof(a[0]);

    printf("정렬 전 배열: ");
    printArray(a, n);

    radixSort(a, n);

    printf("정렬 후 배열: ");
    printArray(a, n);

    return 0;
}

 

10진수 배열 a[]를 기수정렬을 사용해서 정렬했다.

다음은 출력

 

정렬 전 배열: 170 45 75 90 802 24 2 66 
정렬 후 배열: 2 24 45 66 75 90 170 802