package sort;

import java.util.Scanner;

/* 도수 정렬 = 요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘
 * 각 단계에서 배열 요소를 건너뛰지 않고 순서대로 스캔하기에 같은 값에 대해 순서가 바뀌는 일이 없어 안정적인 알고리즘
 * 도수분포표가 필요하기때문에 데이터의 최솟값과 최댓값을 알고 있는 경우에만 사용한다
 * <4단계로 이루어짐>
 * 1.도수분포표 만들기
 * 2.누적도수분포표 만들기
 * 3.목적 배열 만들기
 * 4.배열 복사
 * 단, 3단계에서 배열a를 스캔시 마지막 위치부터가 아닌 처음부터 스캔을 실시하면 중복된 값의 순서가 반대로 바뀌어
 * 안정적이지 않게 된다.
*/
public class Fsort {
	static void fSort(int[] a, int n, int max) {
		// 도수 정렬(0이상 max이하의 값을 입력한다)
		int[] f = new int[max+1];	// 누적용 도수
		int[] b = new int[n];		// 작업용 목적 배열(a배열을 정렬)
		
		for(int i=0; i<n; i++) f[a[i]]++;				// 1단계:도수분포표 만들기
		for(int i=1; i<=max; i++) f[i] += f[i-1];		// 2단계:누적도수분포표 만들기
		for(int i=n-1; i>=0; i--) b[--f[a[i]]] = a[i];	// 3단계:목적 배열 만들기
		for(int i=0; i<n; i++) a[i] = b[i];				// 4단계:배열 복사하기
	}
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		System.out.println("도수 정렬");
		System.out.print("요솟수 : ");
		int nx = stdIn.nextInt();
		int[] x = new int[nx];
		
		for(int i=0; i<nx; i++) {
			do {
				System.out.print("x[" + i + "] : ");
				x[i] = stdIn.nextInt();
			} while(x[i] < 0);
		}
		
		int max = x[0];
		for(int i=1; i<nx; i++)
			if(x[i] > max) max = x[i];
		
		fSort(x, nx, max);		// 배열 x를 도수 정렬
		
		System.out.println("오름차순으로 정렬했습니다.");
		for(int i=0; i<nx; i++)
			System.out.println("x[" + i + "]=" + x[i]);
		
		stdIn.close();
	}
}