[자바] 기수정렬 (Radix sort) 개념과 구현

기수정렬
Radix sort

 

기수정렬

정렬 방식 중 하나이다.

각 원소간 크기를 비교하지 않아서 빠른 시간복잡도를 가지고 있으며, 대신 별도의 메모리 공간이 필요하다.

시간복잡도는 O(dn)이다. 여기서 d는 모든 원소 중 가장 높은 자릿수를 의미한다.

예를들어 가장 높은 자릿수가 10만인 워스트케이스를 생각해보면 이 때 시간복잡도는 100000 x n이 되는것이다.

 

 

 

정렬방식

 

Step 1

1. 별도의 List 혹은 Queue를 만든다.
2. 배열의 각 원소를 List 또는 Queue에 넣는데, 이 때 각 원소의 1의자리 숫자에 해당하는 index를 찾아 배열 순서대로 넣는다.
3. 2번에서 별도의 테이블에 담은 원소들을 다시 초기 배열에 순서대로 넣는다.

 

Step 2

Step 1과 동일하며, 봐야할 자릿수만 다르다.
각 원소의 10의자리 숫자 만큼의 index를 List 또는 Queue에서 찾아 넣는다.
이후에도 자릿수를 100, 1000 늘려가며 원소 중 가장 큰 자릿수만큼 이 과정들을 반복하면 된다.
이것이 기수정렬의 시간복잡도가 O(dn)이라고 불리우는 이유이다.

 

 

코드구현

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

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

        int idx = 0;
        int length = 1; // 알고자하는 각 원소들의 자릿수.  최대자릿수까지 1, 10, 100... 늘려갈것
        int maxLength = getMaxLength(arr); // 배열의 각 원소 중 최대 자릿수를 구하는 메서드

        for (int i = 0; i < maxLength; i++) {
            for (int j = 0; j < arr.length; j++) {
                list.get((arr[j] / length) % 10).offer(arr[j]);
            }   // length번째 자릿수에 맞는 list의 index에 채워넣는다

            for (int j = 0; j < 10; j++) {
                Queue<Integer> queue = list.get(j); 
                // list에 넣은것들을 차례로 queue에 넣고 queue에서 순서대로 꺼내어 다시 초기 arr에 넣는다.
                while (!queue.isEmpty()) {
                    arr[idx++] = queue.poll();
                }
            }

            idx = 0;
            length *= 10; // 우리가 알고자 하는 자릿수를 1에서 시작하여 10, 100... 최대자릿수까지 늘려간다.
        }
    }

    //최대자릿수 구하는 메서드
    public static int getMaxLength(int[] arr) {
        int maxLength = 0;
        for (int i = 0; i < arr.length; i++) {
            int length = (int) Math.log10(arr[i]) + 1; // 자릿수 구하기
            if (length > maxLength) {
                maxLength = length;
            }
        }
        return maxLength;
    }
    
    
    
    public static void main(String[] args) {
    // Test code
    int[] arr = {10, 32, 52, 27, 153, 48, 17, 99, 56};
    radixSort(arr);
    System.out.println(Arrays.toString(arr)); // 출력: [10, 17, 27, 32, 48, 52, 56, 99]
    }
}

 

 

위 코드에서 각 원소들의 자릿수가 지니는 number에 맞게 ArrayList<Queue<Integer>> 의 index에 데이터를 임시저장하였다. 처음에 필요하다고 언급한 별도의 메모리 공간이 이에 해당한다.

아래처럼 ArrayList<ArrayList<Integer>>를 메모리공간으로 할당할 수도 있다.

import java.util.ArrayList;
import java.util.Arrays;

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

        int idx = 0;
        int length = 1;
        int maxLength = getMaxLength(arr);

        for (int i = 0; i < maxLength; i++) {
            for (int j = 0; j < arr.length; j++) {
                list.get((arr[j] / length) % 10).add(arr[j]);
            } 

            for (int j = 0; j < 10; j++) {
                ArrayList<Integer> list2 = list.get(j);
                while (!list2.isEmpty()) {
                    arr[idx++] = list2.get(0);
                    list2.remove(0);
                }
            }

            idx = 0;
            length *= 10;
        }

 

 

지금까지 기수정렬의 개념과 구현을 알아보았다.