도수정렬

---

• 요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘이다.
• 도수 분포표가 필요하기 때문에 최솟값과 최댓값을 미리 알고있는 경우에만 사용할 수 있다.
• 안정적이다.

원리

1. 도수 분포표 만들기

• 10점 만점의 테스트에서 학생 9명의 점수를 나타내는 배열 a가 있다.
• 10점 까지의 점수 내에서 해당 점수에 학생이 몇명이 있는지를 나타내는 배열 f를 만든다.

2. 누적 도수 분포표 만들기

• 10점 까지의 점수 내에서 해당 점수에 학생이 몇명이 있는지를 나타내는 배열 f를 누적된 형태로 만든다.

3. 목적 배열 만들기

• 각각의 점수를 받은 학생이 몇 번째에 위치 하는지 알 수 있다.
• 해당 점수에 여러명이 있을 수 있으니 f의 요소에 1을 빼준 값을 b의 인덱스로 한다.

4. 배열 복사하기

• 배열 b값을 배열 a로 복사한다

코드

// max는 a 배열 요소 중 최댓값이다.
static void fSort(int[] a, int n, int max) {
  int[] f = new int[max + 1]; // 도수 분포 배열
  int[] b = new int[n]; // 목적 배열
  
  // 1단계 도수 분포표 만들기
  for (int i = 0; i < n; i++)
    f[a[i]]++; 
    
  // 2단계 누적 도수 분포표 만들기
  for (int i = 1; i <= max; i++)
    f[i] += f[i - 1];
    
  // 3단계 목적 배열 만들기
  for (int i = n - 1; i >= 0; i--)
    // n-1부터 해야 알고리즘이 안정적이다.
    b[--f[a[i]]] = a[i];
    
  // 4단계 배열 복사하기
  for (int i = 0; i < n; i++)
    a[i] = b[i];
}