기수 정렬(radix sort), 그림으로 쉽게 이해하기

1. 기수 정렬이란?

수들의 자릿값을 활용해, 데이터를 정렬하는 정렬방법
(지금까지 배운 정렬들은 수 들간의 대소 관계를 비교하는 비교 정렬이었지만, 기수 정렬은 데이터 간의 대소 관계를 비교하지 않음.)

시간 복잡도는 O(kn)이다. 여기서 K는 입력으로 주어진 데이터 중 가장 큰 자릿값을 말한다. 코딩테스트에서는 최대값이 10억을 넘어가는 경우가 드물기 때문에 실질적으로 O(N)의 시간안에 정렬이 가능하다는 소리이다.
하지만 강철의 연금술사처럼 등가교환의 원칙이다. 해당 정렬을 구현하기 위해서 원래는 Queue가 10개가 필요해서 메모리를 많이 잡아먹는다. 이러한 메모리 사용량을 줄이기 위해 본 포스팅에서는 누적합 배열을 이용한 구현 방법을 소개하겠다.

2. 원리

0. 세팅

현재 확인 중인 자릿값을 가진 숫자가 얼마나 있는지 개수를 count 하는 배열이 필요
(index - 자릿값 0에서 9, value - 해당 자릿값을 가진 수의 개수)

1. 구현 방식

• (0) 주어진 데이터에서 제일 높은 자릿수 확인 (반복 얼마나 할 것인지 체크)
• (1) 현재 자릿값 기준으로 해당 자릿값을 가진 수의 개수를 세어 자릿값 배열을 완성
• (2) 자릿값 배열의 값을 index = 0에서 부터 누적 시킨다. (누적합 배열로 만들기)
• (3) 다시 주어진 입력 데이터의 맨 끝값부터 확인한다.
• (3-1) 현재 조회 중인 데이터의 누적합 배열의 값을 확인하고, 결과 배열의 index와 그 값이 일치하는 위치에 현재 조회중인 데이터를 넣는다.
  (예를 들어 34 는 누적합 배열의 index = 4인 곳을 보고 있고, 그 값이 3이라면, 결과 배열에서 index = 3인 곳에 34를 집어넣는다.)
• (3-2) 3번의 과정을 통해 결과 배열을 다 만들었으면, 이제 해당 배열을 기준으로 다시 (1)에서 (3)번 과정을 반복한다.

3. 예시

예시에서는 이해를 돕기 위해 누적합 배열과 일반 배열을 나누어 놓았다. 문제를 풀 때는 기호에 따라 두 개를 한 배열에 혼용해서 사용해도 된다.

0. 최대 자릿수 확인하기

해당 문제에서는 803이 3자리로 이루어져 있는 최대값 이다. 따라서 해당 배열을 정렬하기 위해 3번의 반복이 필요하다.

1. 1의 자리로 자릿값 배열 만들기

확인해야할 숫자는 각 원소 당 표시한 자릿값의 수이다.

자릿값 배열을 만들면 위와 같이 된다. 이제 다시 데이터를 끝에서 부터 읽으면서 결과 배열을 채워가겠다.

42의 1의 자리값은 2임으로 누적합 배열에서 index = 2인 곳을 확인한다. 해당 위치의 값은 2임으로 결과 배열의 index = 2인 지점에 42를 집어넣는다. 이후 누적합 배열에서 값을 하나 소모 했음으로, -1 한다. (자릿수가 같은 값이 다음에 들어갈 위치를 정확히 하기 위함)

해당 결과 배열은 1의 자릿수를 기준으로 기수 정렬한 값이다. 이제 해당 배열을 원본으로 다시 10의 자리에 대해서 진행하면 된다.

10의 자리는 첫 시작과 끝만 보여주고 넘어가겠다.

마지막인 100의 자리에 대한 자리값 배열 생성 및 정렬 또한 시작과 끝만 보여주겠다.

보다시피 최종 형태에서는 값이 완전히 정렬 되었다.

4. 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int [] arr = new int [st.countTokens()+1];
        int i = 1;
        while (st.hasMoreTokens()){
            arr[i++] = Integer.parseInt(st.nextToken());
        }
        radix_sort(arr, 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void radix_sort (int [] arr, int digit) {
        //  0. num 배열에 각 숫자 별로 현 자릿수가 무엇인지 기록하기
        int [] nums = new int [10];
        for (int i = 1; i < arr.length; i++) {
            nums[(arr[i]/digit)%10]++;
        }
        // 0. 기저 조건 - 문제에서 줄 수 있는 데이터의 최대 자릿수 + 1 만큼 루프 돌면 빠져나온다.
        if(nums[0] == "[[최대 자릿수 + 1]](문제에 따라 바꾸세요!)") return;
        // 2. 누적합 만들기
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i-1];
        }
        // 3. 현 시점 결과 배열 만들기
        int [] results = new int [arr.length];
        for (int i = arr.length-1; i >= 1; i--) {
            int pos = nums[(arr[i]/digit)%10];
            results[pos] = arr[i];
            nums[(arr[i]/digit)%10]--;
        }
        // 4. 결과 배열 옮기기
        for (int i = 1; i < arr.length; i++) {
            arr[i] = results[i];
        }
        radix_sort(arr, digit*10);
    }
}

예시 속 결과 배열의 시작 index가 1인 것에서 알 수 있듯이 누적합 배열의 값을 그대로 쓸려면 결과배열의 시작 index를 1부터 시작하게 조정해줘야 한다. 내 코드 역시 그렇다. 따라서 arr[0] = 0의 값은 정렬에 사용하지 않은 값이니 무시해주자.