[알고리즘] 1-6. 기수 정렬 [구간 합 이용] (+ 우선순위 큐 이용)

1. 기수 정렬

: 값을 비교하지 않는 정렬로, 값을 놓고 비교할 자릿수를 정한 후 해당 자릿수만 비교

-> 시간 복잡도가 O(kn)으로, 데이터의 자릿수에 영향을 받는다.

-> 시간 복잡도가 가장 짧은 정렬로, 데이터의 개수가 많을 경우 사용된다.

 

(1) 구현 과정

: 값의 자릿수를 나타내는 큐인, 10개의 큐를 이용한 정렬

1. 일의 자릿수 기준으로 배열 원소를 큐에 넣는다.
2. 0번째 큐부터 9번째 큐까지 pop을 진행한다.
3. 십의 자릿수 기준으로 같은 과정 반복
4. 마지막 자릿수를 기준으로 정렬할때까지 반복

 

---

문제 22. 수 정렬하기 3

N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오.

입력
첫 번째 줄에 수의 개수 N(1 <= N <= 10,000,000), 두 번째 줄부터 N개의 줄에 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수다.

출력
첫 번째 줄부터 N개의 줄에 오름차순 정렬한 결과를 1줄에 1개씩 출력한다.

예제 입력

11
215
15
344
372
294
100
8
145
24
198

 

예제 출력

8
15
24
100
145
198
215
294
344
372
831

---

1단계. 문제 분석하기

-> N의 최대 개수가 10,000,000으로 O(nlogn)의 시간복잡도는 사용이 불가능하다.

-> 따라서, O(kn)의 시간 복잡도인 기수 정렬을 사용한다.

 

2단계. 손으로 풀어 보기

: 자릿수가 서로 다른 경우 앞에 0이 채워져 있다고 생각하고, 큐에 삽입한다.

-> 8은 008로 가정하고, 십의 자릿수를 기준으로 0위치의 큐에 삽입

 

3단계. 슈도코드 작성하기

N（정렬할 수 개수）
A（정렬할 배열 선언하기）
for（N의 개수만큼 반복하기）
{
	A 배열 저장하기
}
기수 정렬 함수 수행하기
정렬된 A 배열 출력하기


// 기수 정렬 함수 구현하기
// 변수 선언 부
bucket（현재 자릿수들의 분포를 합 배열의 형태로 알려 주는 배열）
ex: bucket[4] -> 현재 기준 자릿값이 0 ~ 4까지 몇 개의 데이터가 있는지 저장하기
output（임시 정렬을 위한 배열）
jarisu（현재 자릿수를 표현하는 수）
// 로직 부분
while（최대 자릿수만큼 반복하기）
{
    현재 기준 자릿수를 기준으로 A 배열 데이터를 bucket에 count
    합 배열 공식으로 bucket을 합 배열 형태로 변경하기
    for（N의 개수만큼 반복하기）
    {
        bucket값을 이용해 현재 기준 자릿수로 데이터를 정렬하기
        output 배열에 저장하기
    }
    for（N의 개수만큼 반복하기）
    {
    	다음 자릿수 이동을 위해 A 배열에 output 데이터 저장하기
    }
    jarisu = jarisu * 10
}

 

 

package sorting.ch04;

import java.util.Scanner;

public class sorting_q22 {
	public static int[] arr;	
	public void sort(int[] arr, int max) {
		int[] output = new int[arr.length];
		int cipher= 1;
		int cnt = 0;
		//최대 자릿수만큼 반복
		while(cnt!=max) {
			int[] bucket = new int[10];
			//0부터 9까지 이므로, 10개 -> 현재 자리 기준으로 정렬
			
			//일의 자리부터 시작
			for(int i=0;i<arr.length;i++) bucket[(arr[i]/cipher)%10]++;
			
			//합 배열을 이용해 index 계산
			for(int i=1;i<10;i++) bucket[i]+=bucket[i-1];
			
			//현재 자릿수를 기준으로 정렬
			for(int i=arr.length-1;i>=0;i--) {
				output[bucket[(arr[i]/cipher%10)]-1]=arr[i];
				bucket[(arr[i]/cipher)%10]--;
			}
			for(int i=0;i<arr.length;i++) arr[i]=output[i];
			//다음 자릿수로 이동하기 위해 현재 자릿수 기준 정렬 데이터 저장
			
			cipher=cipher*10;
			cnt++;
		}
		

		
		
	}
	public static void main(String[] args) {
		sorting_q22 T = new sorting_q22 ();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		arr = new int[n];
		for(int i=0;i<n;i++) arr[i]=kb.nextInt();
		T.sort(arr,5);
		//수가 10,000보다 같거나 작은 자연수이기 때문에 최대 자릿수가 5이다.
		
		for(int x: arr) System.out.println(x);
	}

}

 

 

 

 

+) 우선순위 큐를 이용한 기수정렬