기수 정렬(RadixSort) 구현

기수 정렬(radix sort)은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다. 자릿수가 고정되어 있으니, 안정성이 있고(이때 데이터들 간의 상대적 순서는 보존되어야 한다.) 시간 복잡도는 O(dn)이다.(d는 가장 큰 데이터의 자리수)

기수 정렬은 비교 연산을 하지 않으며, 무엇보다도 전체 시간 복잡도 역시 O(dn)이어서, 정수와 같은 자료의 정렬 속도가 매우 빠르다. 하지만, 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. 기수 정렬은 정렬 방법의 특수성 때문에, 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 사용 가능할 때에는 매우 좋은 알고리즘이다.

설명 출처 : https://ko.wikipedia.org/wiki/%EA%B8%B0%EC%88%98_%EC%A0%95%EB%A0%AC

code : https://github.com/EomTaeWook/Algorithm/blob/master/Algorithm/Sort/RadixSort.cs

양수 음수 구분 한 다음 합침

namespace Algorithm.Sort

{

    class RadixSort

    {

        public static List<int> Sort(List<int> unsortList)

        {

            return Sort(ref unsortList);

        }

        private static List<int> Sort(ref List<int> unsortList)

        {

            List<Queue<int>> _positiveBucket = new List<Queue<int>>();

            List<Queue<int>> _negativeBucket = new List<Queue<int>>();

            for (int i = 0; i < 11; i++)

            {

                _positiveBucket.Add(new Queue<int>());

                _negativeBucket.Add(new Queue<int>());

            }

            var digit = unsortList.Max().ToString().Length;

            int div = 1, idx = -1;

            for (int i = 0; i < digit; i++, div *= 10)

            {

                for (int ii = 0; ii < unsortList.Count; ii++)

                {

                    idx = unsortList[ii]/ div % 10;

                    if (idx >= 0)

                        _positiveBucket[idx].Enqueue(unsortList[ii]);

                    else

                        _negativeBucket[idx * -1].Enqueue(unsortList[ii]);

                }

                idx = 0;

                for(int ii= _negativeBucket.Count - 1; ii>=0; ii--)

                {

                    while (_negativeBucket[ii].Count > 0)

                        unsortList[idx++] = _negativeBucket[ii].Dequeue();

                }

                for (int ii = 0; ii< _positiveBucket.Count; ii++)

                {

                    while (_positiveBucket[ii].Count > 0)

                        unsortList[idx++] = _positiveBucket[ii].Dequeue();

                }

            }

            return unsortList;

        }

    }

}