기수정렬 구현

기수정렬

데이터의 값을 서로 비교하지 않는 방식으로 정렬한다. 시간복잡도는 Kn으로 정렬 방법중 가장 짧다.(여기서 K는 데이터의 최대 자릿수를 의미함)

핵심아이디어

제일 큰 자릿수를 기준으로 정렬하면 제일 큰 자릿수 기준으로는 순서대로 정렬된다. 또한 이전 자릿수 역시 정렬 되어있으므로 되어 있으므로 정렬이 가능하다.

스택을 사용한 구현과정

1. 큐(FIFO) 10개를 생성한다.(0~9를 나타냄)

2. 일의 자리를 기준으로 10개의 큐에 각 숫자를 삽입한다.

3. 큐에 들어있는 숫자를 0 -> 9 방향으로 pop( )연산을 수행한다.

4. 십의 자리를 기준으로 10개의 큐에 각 숫자를 삽입한다.

5. (2), (3) 과정을 마지막 자릿수까지 반복한다.
   
   

버킷을 사용한 구현과정

일의 자리를 기준으로 정렬을 진행하고 있다고 가정한다.
0~9까지 각 데이터들의 일의자리의 개수를 버킷에 저장한다. 예를들어 일의자리가 3인 배열의 값이 몇 개 저장한다.
현재값의 일의자리가 3이라면 1과2를 모두 합친 인덱스 다음 인덱스에 할당하면 일의 자리를 기준으로는 모든 데이터가 정렬될 것이다.
그러기 위해서는 버킷배열에 0~9까지 각각 몇 개의 값이 들어있는지 확인하고 누적합을 구하여 버킷배열에 다시 저장한다.
따라서 배열을 정렬 할 때 이전자리 까지의 누적합 다음에 현재 값을 저장하면 된다.

구현코드(버킷을 사용)

public class Q22 {

	public static void main(String[] args) throws Exception{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(in.readLine());
		
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(in.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		sort(arr, 10000);
		
		for(int i= 0; i<n; i++) {
			System.out.println(arr[i]);
		}
		
	}
	
	public static void sort(int[] arr, int max) {
		int jarisu =1;
		int[] tmp = new int[arr.length];
		while(jarisu < max) {
			int[] bucket = new int[10];
			for(int i = 0; i<arr.length; i++) {
				bucket[(arr[i]/jarisu)%10] +=1;
			}
			for(int i=1; i<10; i++) {
				bucket[i] += bucket[i-1];
			}
			
			int zero = 0;
			for(int i=0; i<arr.length; i++) {
				//구간합을 이용해 적절한 순서에 수 삽입
				if((arr[i]/jarisu)%10 !=0) {
					tmp[bucket[(arr[i]/jarisu)%10-1]] = arr[i];
					bucket[(arr[i]/jarisu)%10-1] ++;
				}else {
					tmp[zero] = arr[i];
					zero++;
				}
			}
			for(int i=0; i<arr.length; i++) {
				arr[i] = tmp[i];
			}
			jarisu *=10;
		}
	}

}