[알고리즘 정렬] 기수 정렬(Radix Sort)

  기수 정렬(Radix Sort)이란 낮은 자리 수부터 정렬하는 방식입니다. 각 원소 간 비교 연산을 하지 않아 빠른 대신에 기수 테이블을 위한 메모리를 필요로 합니다. 알고리즘 복잡도는 O(dn)입니다. d는 최대 자릿수를 의미합니다. 최악의 경우 원소의 개수보다 최대 자릿수가 더 클 수 있기 때문입니다.

  기수 테이블은 queue 자료구조로 되어 있습니다.

 

정렬되지 않은 데이터

170

45

75

90

2

24

802

66

↓

170

90

2

802

24

45

75

66

↓

2

802

24

45

66

170

75

90

↓

정렬이 끝난 데이터

2

24

45

66

75

90

170

802

 

  기수 정렬 구현 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void radixSort(int[] array) {
        ArrayList<Queue<Integer>> list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            list.add(new LinkedList<>());
        }

        int index = 0;
        int div = 1;
        int maxLen = getMaxLen(array);

        for (int i = 0; i < maxLen; i++) {
            for (int j = 0; j < array.length; j++) {
                list.get((array[j] / div) % 10).offer(array[j]);
            }
            for (int j = 0; j < 10; j++) {
                Queue<Integer> queue = list.get(j);
                while (!queue.isEmpty()) {
                    array[index++] = queue.poll();
                }
            }
            index = 0;
            div = 10;
        }
    }

    public static int getMaxLen(int[] array) {
        int maxLen = 0;
        for (int i = 0; i < array.length; i++) {
            int len = (int)Math.log10(array[i]) + 1;
            if(maxLen < len) {
                maxLen = len;
            }
        }
        return maxLen;
    }
}

  매개 변수로 배열 array를 받는 radixSort 메소드를 생성합니다.

  Queue의 Integer를 제네릭 타입으로 갖는 ArrayList를 생성합니다.

  for문이 10까지 순회합니다. add 메소드를 이용하여 list에 LinkedList를 생성합니다. ArrayList는 기수 테이블을 생성합니다. LinkedList는 해당 기수에 대한 버킷으로 사용합니다. 기수는 자릿수, 버킷은 자릿수에 해당하는 숫자들을 임시로 저장하는 자료구조를 의미합니다.

  변수 index, div, maxLen을 생성합니다. maxLen은 getMaxLen 메소드를 할당받습니다.

  바깥 for문이 maxLen만큼 순회합니다.

  안쪽 첫 번째 for문이 array의 길이만큼 순회합니다. array의 j번째 원소를 10으로 나눈 나머지, 즉 0~9까지 인덱스를 구합니다. 이를 offer 메소드를 이용하여 list에 추가합니다.

  앞서 추가한 값을 순서대로 가져와서 배치할 것입니다. 안쪽 두 번째 for문이 10까지 순회합니다.

  Integer를 제네릭 타입으로 갖는 Queue를 생성합니다. get 메소드를 이용하여 list에서 j번째 원소를 가져온 값을 할당합니다.

  while문이 queue가 비지 않는 동안에 반복합니다. array의 index 번째 원소에 Queue의 마지막 원소를 차례대로 할당합니다.

  다음 작업을 위해 index와 div를 초기화합니다.

  매개 변수로 배열 array를 받는 getMaxLen 메소드를 생성합니다.

  변수 maxLen을 생성합니다.

  바깥 for문이 array의 길이만큼 순회합니다.

  변수 len을 생성합니다. Math 클래스의 log 메소드를 이용합니다. 밑이 10인 로그로 array의 i번째 원소의 길이를 구하고자 하는 것입니다.

  if문에서 maxLen이 len보다 작다면 maxLen에 len을 할당하여, 더 긴 원소의 길이로 갱신해나갑니다.