c# 기수정렬 (radix sort)

기수 정렬은 낮은 자리수부터 비교해 정렬해 간다는 것이 기본 개념입니다.

시간복잡도는 O(dn)인데, d는 가장 큰 데이터의 자리수를 나타냅니다. 

예를 들어서 [ 45, 1, 23, 9999, 678 ] 라는 값이 있을 때, 가장 큰 수의 자리수는 1000이니까 4 가 됩니다.

따라서, 시간복잡도는 O(4n) 입니다. 

기수정렬은 정렬 방법이 자리수를 비교하는 것이기 때문에 부동 소수점 실수 같은 특수한 비교 연산이 필요한

데이터에는 적용할 수 없지만, 정수와 같은 자료의 정렬 속도가 매우 빠릅니다.

단점이라면 데이터 전체 크기의 기수 테이블의 크기만큼 메모리가 더 필요하다는 것이 있겠네요.

 

위키백과에 나온 예를 한번 보겠습니다. 아래와 같은 데이터가 주어졌고 가장 큰 자리수는 100의 자리 (3) 입니다.

첫번째 기수 정렬을 해보겠습니다.

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

데이터의 자리수를 비교해 담을 메모리 공간을 만들었습니다. 

0

1

2

3

4

5

6

7

8

9

첫 번째 기수 정렬에서는 데이터의 1의 자리만 보고 정렬을 수행해서 담습니다.

170 은 1의 자리가 0이니 0번째에 담습니다. 

170
0	1	2	3	4	5	6	7	8	9

다음 45 를 위의 방법과 동일하게 수행해보겠습니다.

170					45
0	1	2	3	4	5	6	7	8	9

이렇게 수행을 하면 다음과 같이 메모리에 데이터가 담겨 있는 것을 확인 할 수 있습니다.

90 170		802 2		24	75 45	66
0	1	2	3	4	5	6	7	8	9

이제 저장된 순서로 데이터를 꺼냅니다. 첫 번째 정렬이 완료되었습니다.

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

두 번째로 데이터의 10의 자리만 보고 정렬을 수행해서 담습니다. 이 때, 10의 자리가 되지 않는 수는 0으로 처리합니다.

802 2		24		45		66	75 170		90
0	1	2	3	4	5	6	7	8	9

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

마지막으로 100의 자리만을 보고 정렬을 수행해서 담습니다.

90  75   66   45   24  2	170							802
0	1	2	3	4	5	6	7	8	9

차례대로 꺼내면 정렬이 완료됩니다.

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

 

 

아래는 코드입니다.

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp
{
    // 문자나 숫자 정렬 가능
    public class RadixSort<T>
    {
        public List<T> RadixMethod(List<T> array)
        {
            var memory = new Queue<T>[10];
            var max = 0;

            for (int i = 0; i < array.Count(); i++)
            {
                var len = array[i].ToString().Length;

                if (len > max)
                    max = len;
            }

            for (int p = 0; p < memory.Length; p++)
            {
                memory[p] = new Queue<T>();
            }

            var num = Math.Pow(10, max);
            
            for (int i = 1; i < num; i*=10)
            {
                for (int j = 0; j < array.Count(); j++)
                {
                    var temp = int.Parse(array[j].ToString());

                    var k = (temp / i) % 10; 

                     memory[k].Enqueue(array[j]);
                }

                array.Clear();

                for (int p = 0; p < memory.Count(); p++)
                {
                    while (memory[p].Count() != 0)
                    {
                        array.Add(memory[p].Dequeue());
                    }
                }
            }

            return array;
        }
    }
}