Unity 개발자를 위한 C# Radix Sort(LSD) 구현

이전 글인 Counting Sort에서는 비교하지 않는 정렬이라는 관점과 함께, 누적합 기반의 Stable(안정 정렬)이 왜 중요한지를 살펴보았습니다. 이 안정성은 단순한 구현 옵션이 아니라, 정렬 결과가 다음 단계에서도 유지되기 위한 전제 조건이었습니다.

그렇다면 자연스럽게 이런 질문이 이어집니다.

“값의 범위(K)가 너무 커서 Counting Sort를 그대로 적용하기 어렵다면, 어떻게 정렬을 이어갈 수 있을까?”

그 해답이 바로 Radix Sort입니다. Radix Sort는 값 전체를 한 번에 정렬하는 대신, 자릿수별로 정렬을 반복하여 최종 순서를 완성합니다.

이번 글에서는 정수(비음수), 10진수, LSD(Least Significant Digit) 방식의 Radix Sort를 개념 → 예제 → 코드 → Unity 테스트 흐름으로 한 편에 정리해 보겠습니다.

※ Radix Sort는 내부적으로 Stable Counting Sort를 반복 사용합니다. 따라서 Counting Sort의 누적합 기반 안정 정렬을 이해하고 있다면, 이 문서의 내용을 훨씬 자연스럽게 따라갈 수 있습니다.

※ Radix라는 용어는 숫자를 구성하는 기준 단위, 즉 기수(base)를 의미하며, Radix Sort는 이 기수를 기준으로 자릿수별 정렬을 반복하는 알고리즘입니다.

1. Radix Sort의 핵심 아이디어

Radix Sort는 숫자 전체를 한 번에 정렬하지 않습니다.
대신 자릿수를 기준으로 정렬을 여러 번 반복합니다.

1의 자리 → 10의 자리 → 100의 자리 → …
각 단계는 반드시 Stable 정렬이어야 함

여기서 핵심은 단 하나입니다.

앞 단계에서 만들어진 정렬 결과가, 다음 단계에서도 그대로 유지되어야 한다.

예를 들어 1의 자리로 먼저 정렬한 결과를, 10의 자리 정렬 과정에서 깨뜨려 버린다면 최종 결과는 틀어집니다. 그래서 Radix Sort에서는 각 자릿수 정렬을 Stable Counting Sort로 수행합니다.

중요한 점은, 각 단계에서 다루는 값의 범위가 전체 값(K)이 아니라 digit(0~9)라는 점입니다. 즉, count 배열의 크기는 항상 10으로 고정됩니다.

2. 예제로 이해하는 Radix Sort (LSD)

다음 예제 배열을 기준으로 단계별로 살펴보겠습니다.

[170, 45, 75, 90, 802, 24, 2, 66]

자릿수 추출은 다음 공식으로 이루어집니다.

digit = (value / exp) % 10

여기서 exp는 1, 10, 100 … 순으로 증가합니다.

① 1의 자리(exp = 1)

먼저 각 값의 1의 자리(digit)를 추출합니다.

이제 이 digit(0~9)를 기준으로 Stable Counting Sort를 수행합니다. 이 단계에서는 값 전체를 비교하지 않고, 1의 자리 숫자만을 사용합니다.

먼저 각 digit의 등장 횟수를 세면 다음과 같습니다.

digit : 0 1 2 3 4 5 6 7 8 9
count : 2 0 2 0 1 2 1 0 0 0

이 count 배열을 누적합으로 변환하면, 각 digit이 결과 배열에서 차지하는 “끝 위치”를 알 수 있습니다.

digit : 0 1 2 3 4 5 6 7 8 9
count : 2 2 4 4 5 7 8 8 8 8

이제 원본 배열을 뒤에서부터 순회하면서, 각 값이 들어갈 정확한 위치에 배치합니다. 이 뒤에서부터의 순회가 바로 Stable 정렬을 보장하는 핵심입니다.

각 값은 count[digit] - 1 위치에 배치되며, 배치가 끝난 뒤에는 해당 digit의 count 값을 1 감소시킵니다.

원본 배열
[170, 45, 75, 90, 802, 24, 2, 66]

// 뒤에서부터 배치
// count[digit] - 1 위치에 배치 후, count[digit] 감소 (Stable)
66  → digit 6 → count[6] = 8 → output[7] 배치 → --count[6] = 7
2   → digit 2 → count[2] = 4 → output[3] 배치 → --count[2] = 3
24  → digit 4 → count[4] = 5 → output[4] 배치 → --count[4] = 4
802 → digit 2 → count[2] = 3 → output[2] 배치 → --count[2] = 2
90  → digit 0 → count[0] = 2 → output[1] 배치 → --count[0] = 1
75  → digit 5 → count[5] = 7 → output[6] 배치 → --count[5] = 6
45  → digit 5 → count[5] = 6 → output[5] 배치 → --count[5] = 5
170 → digit 0 → count[0] = 1 → output[0] 배치 → --count[0] = 0

이처럼 같은 digit을 가진 값들은 뒤에서부터 배치되면서도 서로의 상대적 순서가 유지됩니다. 이 성질이 바로 다음 자릿수 정렬에서도 이전 결과가 보존되는 이유입니다.

이 과정을 모두 거친 뒤의 결과 배열은 다음과 같습니다.

[170, 90, 802, 2, 24, 45, 75, 66]

이 시점에서 배열은 아직 완전히 정렬된 것은 아니지만, “1의 자리 기준으로는 이미 정렬된 상태”가 되었음을 확인할 수 있습니다.

② 10의 자리(exp = 10)

이번에는 위 결과를 그대로 유지한 채 10의 자리를 기준으로 정렬합니다.

이전 결과 배열
[170, 90, 802, 2, 24, 45, 75, 66]

170 → 7
90  → 9
802 → 0
2   → 0
24  → 2
45  → 4
75  → 7
66  → 6

정렬 결과:

[802, 2, 24, 45, 66, 170, 75, 90]

③ 100의 자리(exp = 100)

이전 결과 배열
[802, 2, 24, 45, 66, 170, 75, 90]

802 → 8
2   → 0
24  → 0
45  → 0
66  → 0
170 → 1
75  → 0
90  → 0

정렬 결과:

[2, 24, 45, 66, 75, 90, 170, 802]

이 시점에서 배열은 완전히 정렬됩니다. 각 단계가 Stable이었기 때문에, 이전 단계의 결과가 정확히 누적될 수 있었습니다.

왜 “어라? 다 정렬됐네?”처럼 느껴질까?

Radix Sort(LSD)는 한 번에 전체 순서를 만들지 않습니다. 대신 자릿수(1의 자리 → 10의 자리 → 100의 자리 …)라는 “정보”를 하나씩 추가하면서, 이미 만들어진 질서(앞 단계 결과)를 절대 깨지 않도록 정렬을 진행합니다.

예를 들어 1의 자리 정렬이 끝난 시점에는 배열이 완전히 정렬된 것은 아니지만, 최소한 “1의 자리 기준으로는 이미 정렬된 상태”입니다. 그리고 다음 단계(10의 자리)에서는 값들을 다시 분류하되, 같은 10의 자리를 가진 값들끼리는 기존 순서를 그대로 유지합니다. 이 “기존 순서 유지”가 바로 Stable(안정 정렬) 이해의 핵심입니다.

이렇게 하면 10의 자리 정보가 추가되면서도 1의 자리에서 만들어진 정렬 결과가 유지되고, 이후 100의 자리, 1000의 자리…로 진행될수록 자릿수 정보가 조용히 누적됩니다. 결국 가장 높은 자리까지 처리하고 나면, 숫자의 크기 비교에 필요한 모든 자릿수 정보가 반영되어 특별히 “정렬 완료”를 선언하지 않았는데도 어느 순간 전체 순서가 완성됩니다.

※ 동작을 시각적으로 확인해보기

아래 링크는 Radix Sort(LSD)의 전체 과정을 자릿수(1의 자리 → 10의 자리 → 100의 자리…) 단계별로 시각화해 줍니다. 각 단계에서 값 전체를 비교하는 것이 아니라, 현재 자릿값(digit)만 추출해 분배하고, 그 결과가 다음 단계로 안정적으로(Stable) 누적되는 흐름을 직접 눈으로 확인할 수 있습니다.

특히 아래 포인트를 집중해서 보면, 글에서 설명한 “Stable이 왜 필수인지”가 훨씬 직관적으로 이해됩니다.

각 단계에서 (value / exp) % 10으로 digit(0~9)이 어떻게 뽑히는지
digit 범위가 항상 0~9라서 count 배열이 항상 10칸으로 고정되는 이유
자릿수별 정렬 결과가 Stable하게 유지되어, 이전 단계의 순서가 다음 단계에서 “깨지지 않고” 누적되는 과정
결과적으로 마지막 자릿수까지 처리하면, 특별히 비교를 하지 않았는데도 전체가 정렬되는 원리

https://www.cs.usfca.edu/~galles/visualization/RadixSort.html

3. 시간 복잡도

Radix Sort의 시간 복잡도는 다음과 같이 표현할 수 있습니다.

O(d × (N + b))

이 식은 Radix Sort가 “한 번 정렬하는 비용”을 여러 번 반복한다는 뜻입니다.

N : 정렬할 데이터의 개수
b : 한 자릿수에서 가능한 값의 개수 (기수, 여기서는 0~9 → 10)
d : 정렬을 반복해야 하는 자릿수의 개수

Radix Sort에서는 한 자릿수를 정렬할 때마다 N개의 값을 한 번씩 보고, b(=10) 크기의 count 배열을 사용해 분류를 수행합니다. 이 과정을 자릿수 개수만큼 반복하므로, 전체 시간은 (N + b)가 d번 반복되는 형태가 됩니다.

중요한 점은, Radix Sort가 값끼리 크고 작음을 비교하지 않는다는 것입니다. 따라서 비교 기반 정렬에서 흔히 등장하는 N log N 형태의 비용 구조를 그대로 따르지 않습니다.

하지만 그렇다고 해서 Radix Sort가 항상 빠른 것은 아닙니다. 다음과 같은 조건에서는 오히려 비효율적일 수 있습니다.

숫자의 자릿수가 많을수록(d 증가), 같은 작업을 여러 번 반복해야 함
각 단계마다 결과를 담기 위한 output 배열이 필요하여 메모리 사용과 복사 비용이 발생함
데이터 개수(N)가 매우 적은 경우, 단순한 비교 정렬이 더 빠르게 동작할 수 있음

즉, Radix Sort는 데이터의 크기와 형태가 조건에 맞을 때 강력한 정렬 방식이며, 모든 상황에서 무조건 빠른 정렬 알고리즘은 아닙니다.

4. Stable 정렬이 왜 필수였는가?

Counting Sort에서 배웠던 누적합 + 뒤에서부터 배치 방식은 Radix Sort에서 단순한 구현 디테일이 아닙니다.

Radix Sort에서는 자릿수별 Counting Sort를 항상 Stable 방식으로만 사용합니다.

이 안정성이 깨지는 순간, 앞 단계에서 만든 정렬 순서가 무너지고 Radix Sort는 더 이상 올바른 결과를 보장하지 못합니다.

5. C# Radix Sort 구현

using System;

namespace Daebak.Common.Algorithms.Sorting
{
    public static class RadixSort
    {
        // 제약:
        // - 비음수 정수(0 포함)만 지원
        // - 음수 처리/기수 변경은 확장 주제
        public static void Sort(int[] array)
        {
            if (array == null || array.Length <= 1)
            {
                return;
            }

            int max = array[0];
            for (int i = 1; i < array.Length; i++)
            {
                if (array[i] > max)
                {
                    max = array[i];
                }
            }

            for (int exp = 1; max / exp > 0; exp *= 10)
            {
                DigitCountingSortStable(array, exp);
            }
        }

        private static void DigitCountingSortStable(int[] array, int exp)
        {
            int n = array.Length;
            int[] output = new int[n];
            int[] count = new int[10];

            for (int i = 0; i < n; i++)
            {
                int digit = (array[i] / exp) % 10;
                count[digit]++;
            }

            for (int i = 1; i < 10; i++)
            {
                count[i] += count[i - 1];
            }

            // Stable: 뒤에서부터 배치
            for (int i = n - 1; i >= 0; i--)
            {
                int digit = (array[i] / exp) % 10;
                int pos = count[digit] - 1;
                output[pos] = array[i];
                count[digit]--;
            }

            for (int i = 0; i < n; i++)
            {
                array[i] = output[i];
            }
        }
    }
}

6. Unity 테스트 코드

using UnityEngine;
using Daebak.Common.Algorithms.Sorting;

public class Test_RadixSort : MonoBehaviour
{
    void Start()
    {
        int[] data = { 170, 45, 75, 90, 802, 24, 2, 66 };

        Debug.Log("Before Sort : " + string.Join(", ", data));
        
        RadixSort.Sort(data);
        
        Debug.Log("After Sort : " + string.Join(", ", data));
    }
}

출력 결과

Before Sort : 170, 45, 75, 90, 802, 24, 2, 66
After Sort : 2, 24, 45, 66, 75, 90, 170, 802

7. 마무리

Radix Sort는 비교하지 않는 정렬의 장점을 극대화할 수 있는 알고리즘입니다. 하지만 그 성능과 정확성은 Stable Counting Sort라는 전제 위에서만 성립합니다. Counting Sort를 먼저 배운 이유는, Radix Sort가 그 위에 정확히 쌓아 올려진 알고리즘이기 때문입니다.

※ 다음 글에서는 Bucket Sort를 다루며, 값의 범위나 자릿수가 아니라 입력 값의 분포(distribution)를 활용하는 정렬 방식으로 정렬 알고리즘의 시야를 한 단계 더 확장해 보겠습니다.

저작자표시 비영리 동일조건 (새창열림)

'자료 구조' 카테고리의 다른 글

Unity 개발자를 위한 C# Counting Sort(계수 정렬) 구현 (0)	2026.01.20
Unity 개발자를 위한 C# Heap Sort(힙 정렬) 구현 (0)	2026.01.19
Unity 개발자를 위한 C# Quick Sort(퀵 정렬) 구현 (0)	2026.01.18
대박 게임 개발 연구소(Daebak Game Dev Lab) 소개 (0)	2026.01.15
Unity 개발자를 위한 C# Merge Sort(병합 정렬) 구현 (0)	2026.01.15