[Sort] 기수 정렬(Radix Sort)

기수 정렬(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의 자리 수를 기준으로 정렬합니다!!

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

 

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

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

이렇게 나오네요~

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

기수 정렬 짱입니다!!

 

---

  

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

 

 

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

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

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

RadixMain.java

 

 
package Radix;
 
public class RadixMain {
    public static void main(String[] args) {
        int[] arr = { 69, 10, 30, 2, 16, 8, 31, 22 };
        RadixSort.sortLSD(arr, 2);
    }
}
 

RadixSort.java

 

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

결과는 아래와 같습니다!