도수 정렬

* 도수 정렬
요소의 대소를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘이다.
도수분포표를 이용하기 때문에 if 대소비교문이 필요없이 for문만으로 정렬이 가능하다.

public class fSort {
    //배열 a중 최댓값을 구하여 max로 넘겨준다.
    static void fSort(int[] a, int n, int max) {
        int[] f = new int[max + 1];
        int[] b = new int[n];

        for (int i = 0; i < n; i++) f[a[i]]++; //도수분포표 만들기
        for (int i = 1; i <= max; i++) f[i] += f[i - 1]; //누적 도수분포표 만들기
        //f 배열에 있는 값을 -- 연산자를 사용한 f 배열은 누적도수분포표가 된 상태인데
        //해당 구간의 누적개수합산을 뜻한다.
        //인덱스를 1씩 빼서 동일한 값일 경우 앞서 저장한 부분의 앞칸에 저장되게 하기 위함이다.
        for (int i = n - 1; i >= 0; i--) b[--f[a[i]]] = a[i]; 
        for (int i = 0; i < n; i++) a[i] = b[i]; //a에 b 복사하기
        
    }
}