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의 값은 정렬에 사용하지 않은 값이니 무시해주자.