[C언어 기수 정렬 알고리즘] 기수 정렬 구현하기

💡 이번에는 기수 정렬 하는 법을 배워보았다.

문제

💡 사용자가 입력한 값이 오름차순으로 기수 정렬 되게 코드를 구현하시오

당연히 없는 문제기에 대충 내가 만들었다.

해답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX 10000

void radixSort(int *a, int n) {
    int res[MAX];   // 결과 배열
    int maxValue = 0;
    int exp = 1;

    for (int i = 0 ; i < n ; i++) {
        if (a[i] > maxValue) {
            maxValue = a[i];
        }
    }

    while (maxValue / 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];
        }

        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", &n);
    for (i = 0 ; i < n ; i++) {
        scanf("%d", &a[i]);
    }
    radixSort(a, n);
    for(i = 0 ; i < n ; i++) {
        printf("%d ", a[i]);
    }

    return 0;
}

설명

기수 정렬이란?

Radix Sort라고 하는 기수 정렬이란 자릿수를 기준으로 차례대로 데이터를 정렬하는 알고리즘이다.

각 데이터를 자릿수를 기준으로 분류하므로 가장 큰 자릿수를 D라고 했을 때 𝑂(𝐷𝑁)의 시간 복잡도를 가진다.

위의 원소가 있을 때 먼저 1의 자리부터 체크한다.

원소78425341653034

기수 정렬의 자릿수 배열은 누적으로 쌓이므로 계수 정렬과 헷갈리지 않게 잘 이해해야 한다.

자릿수 배열0123456789

(누적)

1 = 1

1+1 = 2

0

0

1+1+2 = 4

1+1+2+2 = 6

0

1+1+2+2+1 = 7

0

0

위에 따라서 원소를 뒤에서부터 정렬 해준다.

결과값30341843425657

1의 자리를 정렬한 후 10의 자리를 체크한다.

원소30341843425657

자릿수 배열0123456789

(누적)

1 = 1

0

1+1 = 2

1+1+2 = 4

1+1+2+1 = 5

0

1+1+2+1+1 = 6

0

1+1+2+1+1+1 = 7

0

위에 따라서 원소를 뒤에서부터 정렬해준다.

결과값72530343416584

10의 자리를 정렬한 후 100의 자리를 체크한다.

원소72530343416584

자릿수 배열0123456789

(누적)

6

0

0

6+1 = 7

0

0

0

0

0

0

위에 따라서 원소를 뒤에서부터 정렬해준다.

결과값72530346584341

radixSort 함수

void radixSort(int *a, int n) {
    int res[MAX];   // 결과 배열
    int maxValue = 0;
    int exp = 1;  // 1의 자리

    for (int i = 0 ; i < n ; i++) {  // n은 main에서 받은 원소 개수이다.
				// a[i]가 maxValue보다 크다면 a[i] 값이 maxValue가 된다.
        if (a[i] > maxValue) {
            maxValue = a[i];
        }
    }

    while (maxValue / exp > 0) {    // 1의 자리부터 계산한다.
        int bucket[10] = { 0 }; // 자릿수

        for (int i = 0 ; i < n ; i++) { // 자릿수 배열 처리(계수 정렬과 동일하다.)
            bucket[a[i] / exp % 10]++;
        }

        for (int i = 1 ; i < 10 ; i++) {    // 누적 계산
						// 인덱스 0번은 누적계산을 할 필요가 없기 때문에 int i = 1; 부터 시작하였다.
						// 또한 bucket[i - 1]도 동일한 이유 때문이다.
            bucket[i] += bucket[i - 1];
        }

				// n은 main에서 받아온 원소 개수로 인덱스 값을 고려하지 않았기 때문에 n - 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;   // 10이 곱해지기 때문에 while문을 돌때마다 다음 자릿수를 계산하게 된다.
    }
}

계수 정렬에서 사용 할만한 코드와 기수 정렬 알고리즘에서만 사용하는 코드가 섞여있어 코드 주석이 조금 복잡하다.

나도 이해하는 데에 오래걸렸고, 특히 res[--bucket[a[i] / exp % 10]] = a[i]; 이런 코드는 한번에 이해하기가 어려워서 많이 생각해보는 것 같다.

---

마치며..

나는 포스팅을 하는 입장이니 최대한 이해하고 글을 쓰려고 노력한다.

그래서 시간이 더 오래걸리는 것 같기도 하다.

그러면서 배우는 것이 엄청나게 크기 때문에 힘들어도 이 포스팅을 계속 이어나갈 예정이다.

그리고 혹시나 내 블로그에 들어와서 도움을 받는 이가 있다면.. 너무 기분 좋을 것 같다.