[알고리즘] 정렬 5 - 기수 정렬 Radix Sort

목차

정렬

기수 정렬 Radix Sort

기수 정렬은 분배 방식의 정렬 방법으로 정렬할 우너소의 키값에 해당하는 버켓에 원소를 분배하였다가 버켓(큐)의 순서대로 원소를 꺼내는 방법 반복한다. 기수 정렬은 원소의 키를 표현하는 값의 기수 Radix만큼 버켓이 필요하고, 키값의 자릿수만큼 정렬을 반복한다.

 

첫 번째 단계 (가장 낮은 자리의 숫자에 대한 정렬):

• 배열을 가장 낮은 자리의 숫자(1의 자리)에 따라 0부터 9까지의 버켓으로 나눈다.
• 버켓 0: {10, 30}
  버켓 1: {31}
  버켓 2: {2, 22}
  버켓 3: {}
  버켓 4: {}
  버켓 5: {}
  버켓 6: {16}
  버켓 7: {}
  버켓 8: {8}
  버켓 9: {69}
• 버켓의 순서대로 배열을 업데이트한다: {10, 30, 31, 2, 22, 16, 8, 69}

두 번째 단계 (다음 자리의 숫자에 대한 정렬):

• 배열을 다음 자리의 숫자(10의 자리)에 따라 0부터 9까지의 버켓으로 나눈다.
• 버켓 0: {2, 8}
  버켓 1: {10, 16}
  버켓 2: {22}
  버켓 3: {30, 31}
  버켓 4: {}
  버켓 5: {}
  버켓 6: {69}
  버켓 7: {}
  버켓 8: {}
  버켓 9: {}
• 버켓의 순서대로 배열을 업데이트한다: {2, 8, 10, 16, 22, 30, 31, 69}

최종 단계 (가장 높은 자리의 숫자에 대한 정렬):

• 배열을 가장 높은 자리의 숫자(100의 자리)에 따라 0부터 9까지의 버켓으로 나눈다
• 버켓 0: {2, 8, 10, 16, 22, 30, 31, 69}
  버켓 1: {}
  버켓 2: {}
  버켓 3: {}
  버켓 4: {}
  버켓 5: {}
  버켓 6: {}
  버켓 7: {}
  버켓 8: {}
  버켓 9: {}
• 버켓의 순서대로 배열을 업데이트합니다. 이 단계에서는 더 이상 자릿수가 없으므로 최종으로 정렬이 되었다.

최종 정렬된 배열: {2, 8, 10, 16, 22, 30, 31, 69}

기수 정렬은 자릿수별로 정렬을 수행하므로 안정적인 정렬 알고리즘 중 하나이다.

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

#define RADIX 10   // 정렬할 자료들의 키값이 10진수이므로 RADIX를 10으로 정의
#define DIGIT 2    // 정렬할 자료들의 키값이 두 자리이므로 DIGIT를 2로 정의

typedef int element;     // 연결 큐 원소(element)의 자료형을 int로 정의

typedef struct QNode {    // 연결 큐의 노드를 구조체로 정의
    element data;
    struct QNode* link;
} QNode;

typedef struct {        // 연결 큐에서 사용하는 포인터 front와 rear를 구조체로 정의
    QNode* front, * rear;
} LQueueType;


// 공백 연결 큐를 생성하는 연산
LQueueType* createLinkedQueue() {
    LQueueType* LQ;
    LQ = (LQueueType*)malloc(sizeof(LQueueType));
    LQ->front = NULL;
    LQ->rear = NULL;
    return LQ;
}

// 연결 큐가 공백 상태인지 검사하는 연산
int isLQEmpty(LQueueType* LQ) {
    if (LQ->front == NULL) {
        //printf(" Linked Queue is empty! ");
        return 1;
    }
    else return 0;
}

// 연결 큐의 rear에 원소를 삽입하는 연산
void enLQueue(LQueueType* LQ, element item) {
    QNode* newNode = (QNode*)malloc(sizeof(QNode));
    newNode->data = item;
    newNode->link = NULL;
    if (LQ->front == NULL) {        // 현재 연결 큐가 공백 상태인 경우
        LQ->front = newNode;
        LQ->rear = newNode;
    }
    else {                        // 현재 연결 큐가 공백 상태가 아닌 경우
        LQ->rear->link = newNode;
        LQ->rear = newNode;
    }
}

// 연결 큐에서 원소를 삭제하고 반환하는 연산
element deLQueue(LQueueType* LQ) {
    QNode* old = LQ->front;
    element item;
    if (isLQEmpty(LQ)) {
        // 처리가 필요한 부분에 따라 item에 적절한 값을 할당하세요.
        // 예를 들어, item = 0; 또는 item = -1; 등
        return item;
    }
    else {
        item = old->data;
        LQ->front = LQ->front->link;
        if (LQ->front == NULL)
            LQ->rear = NULL;
        free(old);
    }
    return item;
}

// 연결 큐에서 원소를 검색하는 연산
element peekLQ(LQueueType* LQ) {
    element item;
    if (isLQEmpty(LQ)) {
        // 처리가 필요한 부분에 따라 item에 적절한 값을 할당하세요.
        // 예를 들어, item = 0; 또는 item = -1; 등
        return item;
    }
    else {
        item = LQ->front->data;
    }
    return item;
}

// 연결 큐의 원소를 출력하는 연산
void printLQ(LQueueType* LQ) {
    QNode* temp = LQ->front;
    printf(" Linked Queue : [");
    while (temp) {
        printf("%3d", temp->data);
        temp = temp->link;
    }
    printf(" ] ");
}

// 배열 a에 있는 n개 원소에 대해서 기수 정렬을 수행하는 연산
void radixSort(int a[], int n) {
    int i, bucket, d, factor = 1;

    // 정렬할 자료의 기수, 즉 RADIX에 따라 10개의 버킷을 큐로 생성
    LQueueType* Q[RADIX];  // 버킷 큐의 헤드 포인터를 포인터 배열로 선언
    for (bucket = 0; bucket < RADIX; bucket++)
        Q[bucket] = createLinkedQueue();

    // 키값의 자릿수만큼, 즉 두 번 기수 정렬을 반복 수행
    for (d = 0; d < DIGIT; d++) {
        for (i = 0; i < n; i++)
            enLQueue(Q[(a[i] / factor) % RADIX], a[i]);
        for (bucket = 0, i = 0; bucket < RADIX; bucket++)
            while (!isLQEmpty(Q[bucket]))  a[i++] = deLQueue(Q[bucket]);
        printf("\n\n %d 단계 : ", d + 1);
        for (i = 0; i < n; i++)  printf(" %3d", a[i]);

        factor = factor * RADIX;
    }
}

int main(void) {
    int i, list[8] = { 69, 10, 30, 2, 16, 8, 31, 22 };
    int size = sizeof(list) / sizeof(list[0]);    // list 배열의 원소 개수
    printf("\n정렬할 원소 : ");
    for (i = 0; i <= size - 1; i++) printf(" %d", list[i]);
    printf("\n\n <<<<< 기수 정렬 수행 >>>>>>");
    radixSort(list, size);  // 기수 정렬 함수 호출

    getchar();  return 0;
}
--------------------------------
정렬할 원소 :  69 10 30 2 16 8 31 22

 <<<<< 기수 정렬 수행 >>>>>>

 1 단계 :   10  30  31   2  22  16   8  69

 2 단계 :    2   8  10  16  22  30  31  69