ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Sort] 기수 정렬(Radix Sort)
    CSE/Sort 2015. 6. 12. 15:49

    기수 정렬(Radix Sort)













    1단계



     


    2단계


    [출처: gifsoup]





    정의: 분배 방식의 정렬 방법으로 정렬할 원소의 키값에 


    해당하는 버킷에 원소를 분해하였다가 



    버킷의 순서대로 원소를 꺼내는 방법을 반복하며 정렬함.





    그림으로 보시겠습니다!!!




    1단계


















    자 이게 첫 단계의 그림인데요~


    좀 이전의 정렬과는 다른 양상을 보이죠???



    기수 정렬은 기수​를 이용한 정렬이니깐 저렇게 버킷이 존재합니다!!





    1단계에서는 기수 즉, 정렬할 값들의 1의 자리를 가지고 정렬을 시도 합니다!!


    음...


    힌트를 드리자면,


    저 위의 숫자에서 지금 단계에서  중요한건 


    0  1  2  6  8  9


    위의 숫자들이란 겁니다!!!



    버킷의 갯수를 보시면 10개 입니다.


    왜냐하면 0 부터 9까지 넣겠다는 겁니다.


    그래서 정렬할 숫자들의 1의 자리 수를 검사하는 겁니다!!!


    그래서 아래처럼 버킷에 들어가게 되는 거죠!!!




     


    잘 보시면 69는 버킷 9에 들어가있고

    8은 버킷 8

    16은 버킷 6 

    이런식이죠???


    이렇게 정렬 한 후, 버킷0~9까지 


    순서대로


    꺼냅니다!!



    아래와 같이 나오게 됩니다!!







    이렇게 1단계가 1의 자리수를 정렬하면서 끝이나요!!













    2단계






    2단계에서는 그럼 뭘하죠???



    1단계에서는 1의 자리 수를 기준으로 버킷에 넣었다가 뺐습니다.




    네. 이번 단계는 10의 자리 수를 기준으로 정렬합니다!!




    그럼 버킷에 어떻게 들어가는지 볼까요??




     



    위 처럼 들어가게 됩니다!!!




    이걸 순서대로 끄집어 냅니다!!!







    이렇게 나오네요~


    정렬이 다되었스빈!!!!


    기수 정렬 짱입니다!!




    edward_special-37 







      


    이 기수 정렬의 시간 복잡도(Time Complexity)는 아래와 같습니다!



     



     


    여기서 k는 자릿수를 말합니다!!!


    정말 굉장히 빠른 녀석이죠!!!





    소스 코드를 통해 보겠습니다!!!
     



    RadixMain.java


     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
    package Radix;
     
    public class RadixMain {
        public static void main(String[] args) {
            int[] arr = { 69103021683122 };
            RadixSort.sortLSD(arr, 2);
        }
    }
     
    cs



    RadixSort.java


     

    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
     
    package Radix;
     
    import java.util.LinkedList;
     
    import Selection.SelectionSort;
     
    public class RadixSort {
     
        @SuppressWarnings("unchecked")
        private static LinkedList<Integer>[] counter = new LinkedList[] {
                new LinkedList<Integer>(), new LinkedList<Integer>(),
                new LinkedList<Integer>(), new LinkedList<Integer>(),
                new LinkedList<Integer>(), new LinkedList<Integer>(),
                new LinkedList<Integer>(), new LinkedList<Integer>(),
                new LinkedList<Integer>(), new LinkedList<Integer>() };
     
        // 버킷으로 사용할 counter 변수
     
        // maxDigitSymbols는 정렬할 숫자 중에서 가장 많은 자릿수를 갖는 녀석 기준
        public static void sortLSD(int[] array, int maxDigitSymbols) {
            int mod = 10;
            int dev = 1;
            for (int i = 0; i < maxDigitSymbols; i++, dev *= 10, mod *= 10) {
                for (int j = 0; j < array.length; j++) {
                    int bucket = (array[j] % mod) / dev;
                    counter[bucket].add(array[j]);
                }
     
                int pos = 0;
     
                for (int j = 0; j < counter.length; j++) {
                    Integer value = null;
                    while ((value = counter[j].poll()) != null) {
                        array[pos++] = value;
                    }
     
                }
                System.out.println("기수 정렬 " + (i + 1) + " 단계:");
                SelectionSort.printArr(array);
            }
     
        }
     
    }
    cs



    결과는 아래와 같습니다!


     


     



    'CSE > Sort' 카테고리의 다른 글

    [Sort] 힙 정렬(Heap Sort]  (2) 2015.06.12
    [Sort] 기수 정렬(Radix Sort)  (0) 2015.06.12
    [Sort] 합병 정렬(Merge Sort)  (0) 2015.06.12
    [Sort] 셸 정렬(Shell Sort)  (0) 2015.06.12
    [Sort] 퀵 정렬(Quick sort)  (1) 2015.06.12
    [Sort] 삽입 정렬(Insertion sort)  (0) 2015.06.12
    [Sort] 버블 정렬(Bubble Sort)  (0) 2015.06.12

    댓글 0

Designed by Tistory.