도수 정렬

• 요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘
• if문 대신 for문만을 사용해 정렬할 수 있는 매우 아름다운 알고리즘
• 데이터의 비교, 교환 작업이 필요 없어 매우 빠르다.
• 단일 for문만을 사용하여 재귀 호출, 이중 for문이 없어 아주 효율적인 알고리즘
• 하지만 도수분포표가 필요하기 때문에 데이터의 최솟값과 최댓값을 미리 알고 있는 경우에만 사용할 수 있다.
• 각 단계(for문)에서 배열 요소를 건너뛰지 않고 순서대로 스캔하기 때문에 같은 값에 대해서 순서가 바뀌는 일이 없어 안정적인 알고리즘이다.
• 도수 정렬 알고리즘은 도수분포표 작성, 누석도수분포표 작성, 목적 배열 만들기, 배열 복사의 4단계로 이루어진다.

 

10점 만점의 테스트에서 학생 9명의 점수에 대해 도수 정렬하기

1. 도수분포표 만들기 : 각 학생들의 점수가 담긴 배열 a에 대해 각 점수에 해당하는 학생이 몇 명인지를 나타내는 도수분포표를 만든다.
2. 누적도수분포표 만들기 : 도수분포표를 기반으로 0점부터 점수 n까지 몇 명의 학생이 있는지 누적된 값을 나타내는 누적도수분포표를 만든다.
3. 목적 배열 만들기 : 배열 a를 마지막 위치부터 스캔하면서 요솟값과 누적도수분포표 f를 대조하며 정렬을 마친 배열을 만드는 작업
4. 배열 복사하기 : 배열 a는 정렬하기 전 상태이므로 배열 b값을 배열 a로 복사한다.

//도수 정렬(0 이상 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];
    }
    
    //목적 배열 만들기
    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];
    }
}