[2751] 수 정렬하기2 - 기수 정렬
기수정렬이란 이전에 배웠던 버블, 선택, 삽입, 퀵, 병합 등등.. 다른 내부정렬과는 다르게 2-Way 합병정렬에 속한다.
직접 수를 비교하지않고 1의자리비교, 10의자리비교, 100의자리비교 .. -> 를 통해 수를 정렬하는 방법이다.
문제
수 정렬하기 (2750) 문제의 연장선이다.
전체 코드
import java.util.*;
public class algo_3rd {
public static void main(String[] args) {
//메인함수: 입력받고 정렬하기
Scanner sc = new Scanner(System.in);
//입력방식은 Scanner를 사용하였다.
int N = sc.nextInt();
int[] arr = new int[N];
for(int i=0;i<N;i++) { //입력문
arr[i] = sc.nextInt();
}
int[] resArr = radixSort(arr); //radix(기수)Sort를 한 이후의 값을 받아와 새로운 배열로 정의
for (int val : resArr) {
System.out.println(val); //결과출력
}
}
public static int[] radixSort(int[] arr) { //기수정렬
int max = 0;
for(int i=0;i<arr.length;i++){
max = Math.max(arr[i], max);
}
//arr의 원소들 중 가장 큰 값을 찾아서 max변수로 초기화
int cnt = (int)Math.log10(max)+1;
//이후 max를 상용로그로 씌우고 1을더해 자리수를 찾는다.
// System.out.println("max: "+max);
// System.out.println("cnt: "+cnt);
List<Queue<Integer>> buf = new ArrayList<>(); //원소가 큐인 리스트를 만든다.
for (int i = 0; i <= 9; i++) {
Queue<Integer> queue = new LinkedList<>(); //원소는 총 10개의 큐 이다.
buf.add(queue); //리스트에 큐 삽입
}
for (int i = 0; i < cnt; i++) { //각 자릿수에 대해서 진행한다 LSD방식을 따른다 여기선
int Idx = 0; //얘는 큐에 정렬되어있는 수들을 다시 arr에 넣을 때 사용된다.
for (int val : arr) { //arr의 각 원소에 접근한다.
int bufIdx = (int)(val / (int)Math.pow(10, i))%10;
//bufIdx(0~9)를구한다.
//예를들어 값이 131이고 cnt(i)의 값이 0일경우(1의자리) (131 / 1) % 10 = 1 의 값을 얻는다. => 1의자리 비교
//예를들어 값이 254이고 cnt(i)의 값이 1일경우(10의자리) (254 / 10) % 10 = 5 의 값을 얻는다. => 10의자리 비교
buf.get(bufIdx).add(val);
//구했으면 해당 Idx인 큐에 값을 넣는다.
//현재는 모든 원소가 큐에 정렬된 상태이다.
}
for (int j = 0; j <= 9; j++) {
Queue<Integer> queue = buf.get(j);
//각 번호의 큐를 가져온다 (0~9번큐)
int qLength = queue.size(); //사이즈를 조사해 변수로 지정해준다. 만약 빈 큐가 존재할 경우, 골치아프기 때문에 이 변수는 꼭 초기화해야함.
for (int k = 0; k < qLength; k++) {
//해당 순서의 큐를 조사해서 다시 arr에 삽입해준다.
if(!queue.isEmpty()){
arr[Idx] = queue.poll();
Idx++;
}
}
}
}
return arr;
}
}
풀이
015, 123, 554, 972 라는 숫자가 있다고 가정,
1. 먼저 가장 큰 수를 찾는다(972)
2. 그 수의 자릿수를 조사한다(100의자리, 10^2, 세자리수)
3. LSD기수정렬 방식을 사용하여 정렬한다고 했을 때, 1의자리 -> 10의자리 -> 100의자리 순서대로 접근한다.
4. 1의자리를 조사한다. 그리고 각번호에 해당되는 큐에 넣어준다.
5. FIFO방식을 통해 0번큐부터 poll하고 다시 10의 자리를 조사한다.
6. 다시 10의자리의 숫자들을 해당되는 큐에 넣어준다.
7. 위과정을 반복하다보면 결국 정렬된 배열이 탄생한다.
입력
출력
장점과 단점
장점
일단 빠르다. O(dn)의 시간복잡도가 필요하다.
이때 d는 자리수이고 n은 배열의 크기이다.
즉 자릿수 x 원소의 개수 만큼 이동이 이루어지므로 O(dn)의 크기이다.
단점
수를 직접 비교하는 개념이 아니기 때문에, 자릿수가 존재하지 않는(예를들면 부동 소수점)경우에는 사용할 수 없다.
오직 정수부를 비교하는데 사용하는것이 편리하다.
또한 자릿수의 편차가 큰 경우(예를들어 수의 배열이 14, 25783389, 23, 4, 9000234674) 즉 매우 큰수와 매우 작은수가 섞여있는 경우 O(nlogn)인 퀵소트보다 더 효율이 떨어지는 경우가 있다.