07-7 기수 정렬

※ 기수정렬(Radix Sort)

 - 분배 방식의 정렬 방법

 - 정렬할 원소의 키값에 해당하는 버킷(bucket)에 원소를 분배하였다가 버킷의 순서대로 원소를 꺼내는 방법을 반복

 - 원소의 키를 표현하는 값의 기수(radix)만큼의 버킷이 필요하고, 키값의 자리수만큼 기수 정렬을 반복한다.

 - 10진수로 표현된 키값을 가진 원소들을 정렬할 때에는 0~9까지의 10개의 버킷을 이용

 - 키값의 일의 자리에 대해 기수 정렬을 수행하고 그 다음 십의 자리에 대해 기수 정렬을 하고 그 다음 백의 자리에 대해 기수정렬을 하고.... 자리수에 맞게 반복한다.

 - 버킷은 원소들을 순서대로 꺼내어 다음 단계의 기수 정렬을 수행해야 하므로 큐를 사용하여 만든다.

※ 구현

Radix Sort

public class RadixSort {

       Queue[] ql = new Queue[10];

       int[] result;

       int placeValue =1;

       

       public RadixSort(){

              Queue<Integer> q0 = new LinkedList<Integer>();

              Queue<Integer> q1 = new LinkedList<Integer>();

              Queue<Integer> q2 = new LinkedList<Integer>();

              Queue<Integer> q3 = new LinkedList<Integer>();

              Queue<Integer> q4 = new LinkedList<Integer>();

              Queue<Integer> q5 = new LinkedList<Integer>();

              Queue<Integer> q6 = new LinkedList<Integer>();

              Queue<Integer> q7 = new LinkedList<Integer>();

              Queue<Integer> q8 = new LinkedList<Integer>();

              Queue<Integer> q9 = new LinkedList<Integer>();

              

              ql[0] = q0;

              ql[1] = q1;

              ql[2] = q2;

              ql[3] = q3;

              ql[4] = q4;

              ql[5] = q5;

              ql[6] = q6;

              ql[7] = q7;

              ql[8] = q8;

              ql[9] = q9;

       }

       

       public void sorting(int a[]){

              

              if(result ==null){

                     result = a;

              }

              

              int resultIdx =0;

              

              for(int i =0; i<a.length; i++){

                     if(placeValue ==1){

                           int element = result[i]%10;

                           ql[element].add(result[i]);

                     }else{

                           int element = result[i]/placeValue;

                           ql[element].add(result[i]);

                     }

              }

              

              //breaking point

              if(ql[0].size() == result.length){

                     return;

              }

              

              for(int i =0; i<10; i++){

                     while(ql[i].size() != 0){

                           result[resultIdx] = (int) ql[i].poll();

                           resultIdx++;

                     }

              }

              

              placeValue *= 10;

              

              printRadixSort();

              

              sorting(result);

       }

       

       public void printRadixSort(){

              System.out.print("\n정렬된 원소 : ");

              for(int i=0; i <result.length; i++){

                     System.out.print(result[i]+" ");

              }

              System.out.println();

       }

}

Main

public class Main {

       public static void main(String[] args) {

              

              int a[] = {69,10,30,2,16,8,31,22};

              RadixSort rs = new RadixSort();

              System.out.println("\n정렬할 원소 : ");

              for(int i =0; i<a.length; i++){

                     System.out.printf(" %d ", a[i]);

              }

              System.out.println();

              rs.sorting(a);

       }

}