06 정렬 알고리즘 - 기수 정렬(Radix Sort)

기수정렬 (Radix Sort)

---

기수정렬은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘입니다. 기수정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요합니다.

 

■ 정렬 방식

 

1. 0~9 까지의 Bucket(Queue 자료구조의)을 준비한다.

 

2. 모든 데이터에 대하여 가장 낮은 자리수에 해당하는 Bucket에 차례대로 데이터를 둔다.

 

3. 0부터 차례대로 버킷에서 데이터를 다시 가져온다.

 

4. 가장 높은 자리수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복한다.

 

 

 

아래의 8개 데이터에 대하여 기수 정렬을 시도해 보겠습니다. 위의 그림과 같이 각 숫자에 해당하는 Queue공간을 할당하고 진행합니다.

 

먼저 1의 자리 숫자부터 시도를 합니다. 데이터 순서대로 각 1의 자리에 해당되는 Queue에 데이터가 들어가게 됩니다. 15같은 경우는 1의 자리가 5이므로 Queue 5에 들어가는 방식입니다.

 

 

위의 그림처럼 다시 0번 Queue부터 차례대로 데이터를 가지고 와서 원래의 배열에 넣어주게 됩니다.

1의 자리에 대한 정렬이 완료되었습니다. 다음으로는 10의 자리에 대하여 같은 작업을 반복합니다.

 

마찬가지로 각 데이터의 10의 자리에 해당되는 Queue에 데이터를 위치 시킵니다. 그런 다음 0번 Queue부터 차례대로 다시 데이터를 가지고 옵니다.

 

최종적으로 정렬이 완료가 됩니다.

 

 

■ 특징

 

1. 시간 복잡도는 O(dn)

 

2. 자리수가 고정되어 있어서 안정성이 있는 정렬 방식

 

■ 코드 구현

    public void Radix_Sort(int[] data)
    {
        int maxsize = getMaxlength(data);
        ArrayList<Linear_Queue> bucket = new ArrayList();
        int powed=1;
        int index = 0;

        for(int i=0;i<10;i++)        //버킷 생성
        {
            bucket.add(new Linear_Queue(10));
        }
        
        for(int i=1;i<=maxsize;i++)        //자리수가 가장 큰 수만큼 전체 반복문을 반복합니다.
        {
            for(int j=0;j<data.length;j++)    
            {    
                bucket.get((data[j]/powed)%10).EnQueue(data[j]);    //각 자리수의 맞는 index의 bucket에 넣습니다.
            }
            for(int k=0;k<10;k++)        //버킷에서 데이터를 가지고옵니다.
            {
                int bucket_num = bucket.get(k).rear;

                for(int n=0;n<=bucket_num;n++)
                {
                    data[index] = bucket.get(k).DeQueue();
                    index++;
                }
            }
            index =0;
            powed *=10;
        }
    }
    public int getMaxlength(int[] data)
    {
        int maxsize = 0;
        for(int i=0;i<data.length;i++)
        {
            int length = (int)Math.log10((double)data[i])+1;
            if(maxsize <length)
            {
                maxsize = length;
            }
        }
        return maxsize;            //가장 큰 자리수를 반환합니다.
    }
}

 

 

다음 소스는 Queue 자료 구조 Class입니다.

public class Linear_Queue {
    
    int rear = -1;
    int front = 0;
    int maxsize = 0;
    int[] Linear_Queue;
    
    public Linear_Queue(int maxsize)
    {
        this.maxsize = maxsize;
        Linear_Queue = new int[maxsize];
    }
    
    public void EnQueue(int num)
    {
        if(rear != maxsize-1)
        {
            Linear_Queue[++rear] = num;
        }
        else
        {
            System.out.println("데이터 다참");
        }
    }
    
    public int DeQueue()
    {
        if(rear!=front || (rear==0 && front==0))
        {
            int tmp =Linear_Queue[front];
            for(int i=1;i<=rear;i++)
            {
                Linear_Queue[i-1] = Linear_Queue[i];
            }
            rear--;
            return tmp;
        }
        else
        {
            return -1;
        }    
    }
}

 

 

출처 : https://lktprogrammer.tistory.com/48?category=672214