C언어로 구현하는 Radix Sort를 활용한 정수 배열 정렬 방법

Radix Sort는 정렬 알고리즘 중 하나로, 데이터를 자릿수에 따라 분류하여 정렬하는 방식으로 동작합니다. 특히 정수 배열을 정렬하는 데 적합하며, 안정적인 정렬 결과를 제공합니다. 다른 정렬 알고리즘에 비해 특정 데이터 셋에서 뛰어난 성능을 발휘하며, 시간이 아닌 공간 복잡도를 더 많이 활용하는 점이 특징입니다. 본 기사는 Radix Sort의 개념과 원리, 그리고 이를 C언어로 구현하는 방법을 살펴보고 실전 예제까지 다루어 독자의 이해를 돕습니다.

Radix Sort의 개요와 특징


Radix Sort는 정렬 알고리즘 중 하나로, 데이터를 자릿수(또는 자리값)에 따라 정렬하는 방식으로 작동합니다. 가장 낮은 자릿수부터 시작해 높은 자릿수로 진행하며, 각 단계에서 안정적인 정렬을 수행합니다.

Radix Sort의 작동 원리


Radix Sort는 다음과 같은 방식으로 작동합니다:

  1. 데이터의 가장 낮은 자릿수부터 시작하여 해당 자릿수 기준으로 데이터를 정렬합니다.
  2. 자릿수를 하나씩 증가시키며 동일한 과정을 반복합니다.
  3. 마지막 자릿수까지 정렬이 완료되면 전체 배열이 정렬된 상태가 됩니다.

Radix Sort의 시간 및 공간 복잡도

  • 시간 복잡도: ( O(n \cdot k) )
    여기서 ( n )은 데이터의 개수, ( k )는 최대 자릿수입니다.
  • 공간 복잡도: 추가적인 배열을 사용하여 정렬을 수행하므로 ( O(n + k) )의 공간이 필요합니다.

Radix Sort의 특징

  • 안정성: 동일한 값의 순서가 유지되므로 안정적인 정렬 알고리즘에 속합니다.
  • 효율성: 데이터의 자릿수와 범위가 제한적인 경우 매우 빠른 정렬을 제공합니다.
  • 적용 범위: 정수 및 고정된 자릿수의 데이터 정렬에 적합합니다.

Radix Sort는 특히 데이터가 많은 경우 또는 정수형 데이터를 정렬할 때 효율적인 선택지로 사용됩니다.

Radix Sort의 핵심 단계 설명


Radix Sort는 데이터를 자릿수 기준으로 반복적으로 정렬하여 전체 배열을 정렬합니다. 이 과정은 세 가지 주요 단계로 구성됩니다.

1. 자릿수별 분류 (Counting Sort 활용)


Radix Sort는 내부적으로 Counting Sort를 활용하여 각 자릿수에 대한 안정적인 정렬을 수행합니다.

  • 데이터를 0~9의 값으로 그룹화합니다.
  • 각 값의 개수를 세고 누적 합을 계산하여 해당 데이터의 정렬된 위치를 찾습니다.
  • 이를 통해 자릿수 기준으로 데이터를 안정적으로 정렬합니다.

2. 자릿수 증가


가장 낮은 자릿수(1의 자리)부터 시작하여 높은 자릿수로 이동하며 반복적으로 정렬합니다.

  • 첫 번째 단계에서는 1의 자릿수를 기준으로 정렬합니다.
  • 이후 10의 자리, 100의 자리 등으로 자릿수를 점진적으로 증가시킵니다.

3. 최종 배열 조합


모든 자릿수에 대해 정렬이 완료되면 최종 배열이 정렬된 상태로 나타납니다.

  • 각 자릿수 정렬 과정에서 데이터 순서가 유지되므로 안정성이 보장됩니다.

단계별 예제


정렬할 배열: [170, 45, 75, 90, 802, 24, 2, 66]

  1. 1의 자릿수 기준 정렬: [170, 90, 802, 2, 24, 45, 75, 66]
  2. 10의 자릿수 기준 정렬: [802, 2, 24, 45, 66, 170, 75, 90]
  3. 100의 자릿수 기준 정렬: [2, 24, 45, 66, 75, 90, 170, 802]

이처럼 각 단계에서 자릿수를 기준으로 데이터를 분류하고 정렬하여 전체 배열을 완성합니다.

C언어에서 Radix Sort 구현 준비


Radix Sort를 구현하기 위해 필요한 데이터 구조와 함수 선언, 초기화 작업을 설정합니다. 이 단계에서는 알고리즘 구현에 필요한 핵심 요소를 준비합니다.

필요한 데이터 구조

  1. 배열: 정렬할 데이터를 저장하는 배열입니다.
  2. 보조 배열: 자릿수 기준으로 정렬된 데이터를 임시로 저장하는 데 사용됩니다.
  3. 카운팅 배열: 각 자릿수 값(0~9)의 빈도를 저장합니다.

필요한 함수 선언

  1. getMax() 함수
    배열 내에서 가장 큰 값을 찾아 최대 자릿수를 계산하는 함수입니다.
   int getMax(int arr[], int n);
  1. countingSort() 함수
    주어진 자릿수를 기준으로 배열을 정렬하는 함수입니다.
   void countingSort(int arr[], int n, int exp);
  1. radixSort() 함수
    Radix Sort의 메인 알고리즘을 구현하는 함수입니다.
   void radixSort(int arr[], int n);

코드 예시

#include <stdio.h>

// 배열에서 최대값을 찾는 함수
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

초기화 작업

  1. 배열 초기화
    정렬 대상 데이터를 배열로 선언하고 초기화합니다.
   int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
   int n = sizeof(arr) / sizeof(arr[0]);
  1. 함수 호출
    알고리즘 실행을 위한 준비를 마친 후 함수 호출로 Radix Sort를 실행합니다.
   radixSort(arr, n);

이 단계에서 데이터 구조와 함수를 준비하고 초기화를 완료하면 Radix Sort 구현을 시작할 수 있습니다.

자릿수별 정렬을 위한 보조 함수 구현


Radix Sort의 핵심 단계는 각 자릿수를 기준으로 데이터를 정렬하는 것입니다. 이를 위해 보조 함수인 countingSort()를 구현합니다. 이 함수는 특정 자릿수(1의 자리, 10의 자리 등)에 따라 배열을 정렬합니다.

countingSort() 함수의 목적


주어진 자릿수를 기준으로 Counting Sort 알고리즘을 적용하여 배열을 안정적으로 정렬합니다.

구현 단계

  1. 카운팅 배열 초기화
    자릿수 값(0~9)의 빈도를 저장할 카운팅 배열을 초기화합니다.
  2. 빈도 계산
    입력 배열의 각 요소에서 주어진 자릿수 값을 추출하여 빈도를 계산합니다.
  3. 누적 합 계산
    카운팅 배열을 누적 합으로 변환하여 각 자릿수 값의 정렬된 위치를 결정합니다.
  4. 보조 배열에 데이터 정렬
    입력 배열을 순회하며 정렬된 순서로 보조 배열에 복사합니다.
  5. 원래 배열 업데이트
    보조 배열의 데이터를 원래 배열로 복사하여 정렬된 상태로 갱신합니다.

countingSort() 함수 구현

#include <stdio.h>
#include <string.h>

void countingSort(int arr[], int n, int exp) {
    int output[n]; // 정렬된 데이터를 저장할 보조 배열
    int count[10] = {0}; // 카운팅 배열 초기화 (0~9)

    // 각 자릿수 값을 기준으로 빈도 계산
    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / exp) % 10; // 자릿수 값 추출
        count[digit]++;
    }

    // 누적 합 계산
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // 데이터를 보조 배열에 정렬
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10; // 자릿수 값 추출
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    // 보조 배열의 데이터를 원래 배열로 복사
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

코드 동작 예시


입력 배열: [170, 45, 75, 90, 802, 24, 2, 66]
1의 자릿수 정렬 후: [170, 90, 802, 2, 24, 45, 75, 66]
10의 자릿수 정렬 후: [802, 2, 24, 45, 66, 170, 75, 90]
100의 자릿수 정렬 후: [2, 24, 45, 66, 75, 90, 170, 802]

결론


countingSort() 함수는 각 자릿수별로 배열을 정렬하여 Radix Sort의 핵심 동작을 수행합니다. 이 함수는 안정성을 유지하며, Radix Sort의 효율성을 보장합니다.

메인 Radix Sort 알고리즘 구현


Radix Sort의 메인 로직은 배열의 최대 자릿수를 구하고, 각 자릿수에 대해 countingSort() 함수를 호출하는 구조로 이루어집니다. 이 과정은 배열이 완전히 정렬될 때까지 반복됩니다.

Radix Sort의 구현 흐름

  1. 배열의 최대값을 계산하여 정렬에 필요한 최대 자릿수를 결정합니다.
  2. 1의 자리부터 시작하여 각 자릿수별로 countingSort()를 호출합니다.
  3. 모든 자릿수에 대해 정렬이 완료되면 최종적으로 정렬된 배열이 반환됩니다.

radixSort() 함수 구현

#include <stdio.h>

// Radix Sort 메인 함수
void radixSort(int arr[], int n) {
    // 배열 내 최대값 계산
    int max = getMax(arr, n);

    // 자릿수별로 countingSort 호출
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

// 배열에서 최대값을 찾는 함수
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

코드 설명

  1. getMax() 함수
    배열의 최대값을 찾아 최대 자릿수를 계산하는 데 사용됩니다.
    예: 배열 [170, 45, 75]의 최대값은 170이며, 1의 자리, 10의 자리, 100의 자리가 존재합니다.
  2. 자릿수 반복 루프
    for (int exp = 1; max / exp > 0; exp *= 10)
  • exp는 자릿수를 나타내며, 1의 자리부터 시작하여 10씩 증가합니다.
  • max / exp > 0 조건은 최대 자릿수만큼 루프를 반복하도록 보장합니다.
  1. countingSort() 호출
    각 자릿수별로 정렬을 수행하여 배열을 점진적으로 정렬합니다.

작동 예제


입력 배열: [170, 45, 75, 90, 802, 24, 2, 66]

  1. 1의 자릿수 기준 정렬 후: [170, 90, 802, 2, 24, 45, 75, 66]
  2. 10의 자릿수 기준 정렬 후: [802, 2, 24, 45, 66, 170, 75, 90]
  3. 100의 자릿수 기준 정렬 후: [2, 24, 45, 66, 75, 90, 170, 802]

결론


radixSort() 함수는 전체 Radix Sort 알고리즘의 중심 역할을 수행합니다. 이 함수는 각 자릿수별로 데이터를 정렬하고, 모든 자릿수에 대해 정렬이 완료되면 최종 정렬된 배열을 반환합니다. 이를 통해 Radix Sort의 단계별 동작을 완성할 수 있습니다.

구현된 알고리즘 테스트


Radix Sort를 성공적으로 구현한 후, 다양한 정수 배열을 사용하여 알고리즘이 올바르게 작동하는지 테스트합니다. 테스트는 배열의 크기, 데이터 범위, 음수 포함 여부 등을 고려하여 설계합니다.

테스트 코드


다음은 Radix Sort 알고리즘을 테스트하는 코드입니다.

#include <stdio.h>

// Radix Sort 및 보조 함수들 선언
void countingSort(int arr[], int n, int exp);
void radixSort(int arr[], int n);
int getMax(int arr[], int n);

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

// 메인 함수
int main() {
    // 테스트 케이스 1: 기본 배열
    int arr1[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    printf("Original array 1: ");
    printArray(arr1, n1);
    radixSort(arr1, n1);
    printf("Sorted array 1: ");
    printArray(arr1, n1);

    // 테스트 케이스 2: 음수와 양수 포함
    int arr2[] = {23, -5, 0, 89, -123, 45, -12};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    printf("\nOriginal array 2: ");
    printArray(arr2, n2);
    // Radix Sort는 음수를 처리하지 않으므로, 이를 확장해야 합니다.

    // 테스트 케이스 3: 큰 배열
    int arr3[] = {3000, 1, 432, 56, 10000, 7, 89, 0};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    printf("\nOriginal array 3: ");
    printArray(arr3, n3);
    radixSort(arr3, n3);
    printf("Sorted array 3: ");
    printArray(arr3, n3);

    return 0;
}

테스트 결과

  1. 테스트 케이스 1: 기본 배열
  • 입력: [170, 45, 75, 90, 802, 24, 2, 66]
  • 출력: [2, 24, 45, 66, 75, 90, 170, 802]
  1. 테스트 케이스 2: 음수와 양수 포함
  • 현재 알고리즘은 음수를 처리하지 못합니다.
  • 이를 해결하기 위해 음수와 양수를 분리하거나, 오프셋을 추가로 적용하는 방식이 필요합니다.
  1. 테스트 케이스 3: 큰 배열
  • 입력: [3000, 1, 432, 56, 10000, 7, 89, 0]
  • 출력: [0, 1, 7, 56, 89, 432, 3000, 10000]

결론


Radix Sort는 정수 배열에 대해 안정적이고 효율적으로 동작합니다. 그러나 기본 구현은 음수를 처리하지 못하므로, 음수 데이터가 포함된 배열을 처리하려면 추가 확장이 필요합니다. 다양한 입력 배열로 테스트를 반복하여 구현의 안정성을 확인할 수 있습니다.

Radix Sort의 장점과 한계


Radix Sort는 특정 상황에서 매우 효율적인 정렬 알고리즘으로, 특히 정수 데이터 정렬에 적합합니다. 하지만 모든 경우에 이상적이지는 않습니다. 이 섹션에서는 Radix Sort의 주요 장점과 한계를 분석하고, 다른 정렬 알고리즘과 비교합니다.

Radix Sort의 장점

  1. 안정적인 정렬
  • 동일한 값의 상대적 순서를 유지하므로 안정적인 정렬 알고리즘으로 분류됩니다.
  • 안정성은 중복된 키가 포함된 데이터에서 중요한 속성입니다.
  1. 효율성
  • 데이터가 정수이거나 고정된 자릿수를 가지는 경우 ( O(n \cdot k) )의 시간 복잡도를 가지며, 이는 비교 기반 정렬 알고리즘(( O(n \log n) ))보다 효율적일 수 있습니다.
  • ( k )는 데이터의 최대 자릿수입니다.
  1. 대규모 데이터 처리에 적합
  • 데이터의 범위가 작고 자릿수가 제한적일 때 매우 빠른 속도를 제공합니다.
  • 대량의 정수 데이터를 정렬하는 데 유리합니다.

Radix Sort의 한계

  1. 음수 처리의 어려움
  • 기본 구현에서는 음수를 처리하지 못하므로 추가적인 논리가 필요합니다.
  • 예를 들어, 음수와 양수를 분리한 후 각각 정렬하고 병합해야 합니다.
  1. 공간 복잡도
  • 추가 배열(보조 배열 및 카운팅 배열)을 사용하므로 ( O(n + k) )의 추가 공간이 필요합니다.
  • 데이터 크기가 큰 경우 메모리 사용량이 늘어날 수 있습니다.
  1. 범용성 부족
  • 문자열, 부동소수점 숫자, 기타 복잡한 데이터 타입에는 적합하지 않습니다.
  • 자릿수나 데이터 범위가 제한되지 않은 경우 효율이 떨어질 수 있습니다.
  1. 데이터 의존성
  • 데이터의 최대값(자릿수)에 따라 성능이 달라질 수 있습니다.
  • 자릿수가 큰 경우 ( k )가 증가하여 성능이 저하될 가능성이 있습니다.

다른 알고리즘과의 비교

  1. 퀵 정렬 (Quick Sort)
  • 시간 복잡도: 평균 ( O(n \log n) ), 최악의 경우 ( O(n^2) )
  • 불안정한 정렬 알고리즘
  • Radix Sort보다 범용적이지만, 데이터 범위가 제한된 경우 Radix Sort가 더 효율적
  1. 병합 정렬 (Merge Sort)
  • 시간 복잡도: ( O(n \log n) )
  • 안정적인 정렬 알고리즘
  • Radix Sort와 달리 음수와 문자열도 처리 가능
  1. 힙 정렬 (Heap Sort)
  • 시간 복잡도: ( O(n \log n) )
  • 불안정한 정렬 알고리즘
  • Radix Sort보다 메모리 사용량이 적지만, 안정성이 필요한 경우 Radix Sort가 유리

결론


Radix Sort는 데이터의 범위가 제한적이고 정수가 주어진 경우 가장 효율적인 선택 중 하나입니다. 하지만 음수 데이터나 복잡한 데이터 타입을 처리하기 위해서는 확장이 필요합니다. 알고리즘 선택 시 데이터의 특성과 요구사항을 고려하여 Radix Sort를 적용해야 합니다.

Radix Sort 구현의 최적화 방법


Radix Sort는 기본적으로 효율적인 정렬 알고리즘이지만, 구현을 최적화함으로써 성능을 더욱 향상시킬 수 있습니다. 이 섹션에서는 Radix Sort를 최적화하기 위한 다양한 기법과 개선 방안을 소개합니다.

1. 동적 메모리 할당 최소화


기본 Radix Sort는 보조 배열과 카운팅 배열을 자릿수별로 생성합니다. 배열의 크기가 크거나 자릿수 범위가 넓을 경우, 반복적으로 메모리를 할당하는 것은 성능을 저하시킬 수 있습니다.

  • 최적화 방법: 정렬 과정에서 사용할 보조 배열과 카운팅 배열을 한 번만 할당하고, 자릿수 정렬마다 재사용합니다.
int output[n];   // 정렬 결과 저장용 배열
int count[10];   // 자릿수 값 빈도 저장용 배열

2. 데이터 범위 제한 활용


데이터의 범위가 작은 경우, 정렬할 자릿수를 줄일 수 있습니다. 예를 들어, 배열의 최대값이 999라면 3개의 자릿수만 처리하면 됩니다.

  • 최적화 방법: 최대값을 기반으로 필요한 자릿수만 처리합니다.
int max = getMax(arr, n);
for (int exp = 1; max / exp > 0; exp *= 10) {
    countingSort(arr, n, exp);
}

3. 캐시 활용


보조 배열과 카운팅 배열을 메모리 친화적으로 배치하여 캐시 적중률을 높입니다.

  • 배열을 연속된 메모리 공간에 저장하고, 데이터 접근 순서를 최적화합니다.

4. 멀티스레딩 적용


Radix Sort의 각 자릿수별 정렬 작업은 독립적이므로 멀티스레딩을 활용하여 병렬로 처리할 수 있습니다.

  • 최적화 방법: 자릿수별 정렬 작업을 스레드로 분리하고, 각각의 결과를 병합합니다.

5. 자릿수 기준의 분포 최적화


데이터가 특정 자릿수 값에 편향되어 있는 경우, 카운팅 배열을 동적으로 조정하여 불필요한 작업을 줄일 수 있습니다.

  • : 데이터가 0~5의 자릿수 값만 사용한다면, 카운팅 배열을 크기 6으로 제한합니다.

6. 음수 데이터 처리


기본 Radix Sort는 양수만 처리합니다. 음수를 처리하기 위해 다음과 같은 방법을 사용할 수 있습니다:

  1. 음수와 양수를 분리한 후 각각 정렬
  2. 정렬 결과를 병합하여 최종 배열 생성
void handleNegativeNumbers(int arr[], int n) {
    int positives[n], negatives[n];
    int posCount = 0, negCount = 0;

    // 양수와 음수 분리
    for (int i = 0; i < n; i++) {
        if (arr[i] >= 0) positives[posCount++] = arr[i];
        else negatives[negCount++] = -arr[i];
    }

    // 각각 Radix Sort 적용
    radixSort(positives, posCount);
    radixSort(negatives, negCount);

    // 음수 역순으로 결합
    for (int i = 0; i < negCount; i++) arr[i] = -negatives[negCount - i - 1];
    for (int i = 0; i < posCount; i++) arr[negCount + i] = positives[i];
}

7. 알고리즘 자체의 병렬화


자릿수 정렬 단계에서 각 값 그룹(0~9)을 병렬로 처리할 수 있도록 개선합니다. 이를 통해 대규모 데이터를 효율적으로 정렬할 수 있습니다.

결론


Radix Sort의 최적화를 통해 메모리 사용량을 줄이고, 데이터 분포 및 범위를 효율적으로 활용하며, 멀티스레딩을 적용할 수 있습니다. 이러한 최적화 기법은 데이터 크기와 시스템 환경에 따라 유연하게 선택하여 적용해야 합니다.

요약


Radix Sort는 정수 데이터를 자릿수별로 안정적으로 정렬하는 강력한 알고리즘으로, 특정 데이터 셋에서 비교 기반 정렬보다 효율적입니다. 본 기사에서는 Radix Sort의 원리, 구현, 테스트, 최적화 방법까지 다루며, 이를 통해 대규모 데이터 정렬을 효과적으로 수행할 수 있는 방법을 제시했습니다. Radix Sort를 확장하여 음수 처리와 멀티스레딩 등을 적용하면 더 넓은 범위에서 활용할 수 있습니다.