[자료구조] Radix Sort

 

Radix Sort

• 자릿수로 숫자를 분류해서 정렬하는 방식 

ex) 

012, 421, 046, 674, 103, 502, 007, 100, 021, 545를 Radix Sort

1. 일의 자리로 i번 리스트에 순서대로 저장하기. 

 

0	100
1	421, 021
2	012, 502
3	103
4	674
5	545
6	046
7	007
8
9

 

-> 100, 421, 021, 012, 502, 103, 674, 545, 046, 007

 

 

2. 100, 421, 021, 012, 502, 103, 674, 545, 046, 007을

십의 자리로 리스트에 순서대로 저장하기. 

 

0	100, 502, 103, 007
1	012
2	421, 021
3
4	545, 046
5
6
7	674
8
9

 

-> 100, 502, 103, 007, 012, 421, 021, 545, 046, 674

 

 

3. 100, 502, 103, 007, 012, 421, 021, 545, 046, 674을

백의 자리로 리스트에 순서대로 저장하기.

 

0	007, 012, 021, 046
1	100, 103
2
3
4	421
5	502, 545
6	674
7
8
9

 

-> 007, 012, 021, 046, 100, 103, 421, 502, 545, 674

 

Radix Sort를 하려고 리스트 10개를 사용함. 

한 리스트에 원소가 다 몰릴 수도 있으니 공간 낭비 심함. 

Radix Sort는 개념 이해만 하고 넘어가기. 

 

 

Radix Sort 구현

using System;
using System.Text;

namespace 정렬
{
    internal class 기수정렬
    {
        static StreamReader sr = new StreamReader(Console.OpenStandardInput());
        static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
        static StringBuilder sb = new StringBuilder();

        // 데이터 개수, 배열 초기화 
        static int n = 15;
        static int[] arr = { 12, 421, 46, 674, 103, 502, 7, 100, 21, 545, 722, 227, 62, 91, 240 };

        // 최대 자릿수 
        static int d = 3;
        static int[] p10 = new int[3];

        // x의 10^a 자리 값 반환 메서드 
        static int DigitNum(int x, int a)
        {
            return (x / p10[a]) % 10;
        }

        // 0~9까지의 버킷(리스트) 생성
        static List<int>[] l = new List<int>[10];

        static void Main(string[] args)
        {
            // 10의 거듭제곱 미리 계산
            p10[0] = 1;
            for (int i = 1; i < d; i++)
                p10[i] = p10[i - 1] * 10;

            // 리스트 배열 초기화
            for (int i = 0; i < 10; i++)
                l[i] = new List<int>();

            // 자릿수만큼 반복 (1의 자리 -> 10의 자리 -> 100의 자리)
            for (int i = 0; i < d; i++)
            {
                // 리스트 비우기
                for (int j = 0; j < 10; j++)
                    l[j].Clear();

                // 1. 각 수를 현재 자릿수에 맞는 리스트에 넣기.
                for (int j = 0; j < n; j++)
                {
                    int digit = DigitNum(arr[j], i); // arr[j]의 10^i 자리
                    l[digit].Add(arr[j]);
                }

                // 2. 0번 리스트부터 차례대로 꺼내어 원래 배열에 채우기.
                int idx = 0;
                for (int j = 0; j < 10; j++)
                {
                    foreach (var x in l[j])
                        arr[idx++] = x;
                }
            }

            for (int i = 0; i < n; i++)
                sb.Append($"{arr[i]} ");

            sw.WriteLine(sb.ToString());

            sr.Close();
            sw.Close();
            sb.Clear();
        }
    }
}

 

 

Comparison Sort, Non-comparison Sort

• Comparison Sort = 원소들끼리 크기를 비교하는 정렬
  • ex) Bubble Sort, Merge Sort, Quick Sort
• Non-Comparison Sort = 원소들끼리 크기를 비교하지 않는 정렬
  • ex) Counting Sort, Radix Sort 

 

지금까지 정렬을 배웠다. 그런데.. 코딩테스트에서는 정렬을 직접 구현하면 안된다. 

문제 풀이 시간에 직접 구현 시간이 추가가 될 수 있고, 구현한 코드가 예외처리를 잘못해 문제풀이 시간이 늘어날 수 있고, 직접 구현으로 인해 다른 문제를 풀 수 있는 시간이 줄어들 수 있기 때문.