[Algorithm] 기수 정렬 (Radix Sort)

I. 기수 정렬 (Radix Sort)의 개요

가. 기수 정렬의 정의

레코드를 비교하지 않고 준비된 버킷을 이용하여 정렬하는 방법

 

나. 기수 정렬의 특징

• O (n log2 n) 이라는 이론적인 하한선을 깰 수 있는 유일한 방법
• 시간 복잡도 : O(kn) k : 버킷 수
• 정렬 레코드 타입 제한

 

Ⅱ. 기수 정렬의 개념 및 사례

가. 기수 정렬의 개념

기수 정렬의 개념

 

 

나. 기수 정렬 사례 (Sorting a sequence of 4-bit integers)

기수 정렬 사례 (Sorting a sequence of 4-bit integers)

 

코드 구현

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

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입니다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

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; } } }