1. 개념

주어진 데이터 중에서 자신보다 작거나 같은 값을 갖는 데이터의 개수를 계산하여 정렬할 위치를 찾아 정렬하는 방식

• 입력값이 어떤 작은 정수 범위 내에 있다는 것을 알고 있는 경우 적용 가능
• 임의의 값 k보다 작거나 같은 값을 갖는 데이터의 개수를 계산
  → 정렬 순서상 k의 마지막 위치에 존재
• 자신보다 작거나 같은 값을 갖는 데이터의 개수를 효율적으로 계산하는 방법
  → 입력값이 출현하는 횟수의 누적값을 계산
  1. 입력값의 범위(a~b)에 해당하는 크기의 배열(COUNT[a..b])을 할당
  2. 주어진 값들을 한 번 쭉 훑음

2. 과정

1. 입력 배열을 순회하며 각 값의 등장 횟수를 세어준다. 이때 각 값이 등장한 횟수를 보조 배열에 기록한다.
2. 보조 배열을 순회하며 각 값의 누적 등장 횟수를 계산한다. 이는 정렬된 배열에서 해당 값이 위치해야 할 인덱스를 나타낸다.
3. 입력 배열을 역순으로 순회하면서 각 값에 해당하는 인덱스를 찾아서 정렬된 배열에 값을 배치한다. 이때 보조 배열을 참조하여 값을 배치한다.
4. 정렬된 배열을 반환한다.

3. 구현

public static void countingSort(int[] array) {
	/**
	 * 입력 배열 내 최대값 구하기
     * - 최대값까지만 등장 횟수를 구하기 때문(보조 배열의 크기 제한)
	 */
    int max = Arrays.stream(array).max().getAsInt();
    
	// 보조 배열을 생성하여 각 값의 등장 횟수 기록
    int[] count = new int[max + 1];
    for (int number : array) {
    	count[number]++;
    }
    
    // 보조 배열을 업데이트하여 배열 내 값의 누적 등장 횟수 계산
    for (int index = 1; index < count.length; index++) {
    	count[index] += count[index - 1];
    }
    
    // 정렬된 결과를 저장할 배열 생성
    int[] sortedArray = new int[array.length];
    
    // 입력 배열을 역순으로 순회하면서 정렬된 결과를 저장
    for (int index = array.length - 1; index >=0; index--) {
    	int number = array[index];
        int sortedIndex = count[number] - 1;	// 현재 값이 정렬된 배열에서 위치해야 할 인덱스
        sortedArray[sortedIndex] = number;
        count[number]--;	// 동일한 값에 대해 정렬된 위치가 변경되었기 때문에 누적 등장 횟수 감소
    }
    
    // 정렬된 배열을 입력 배열에 복사
    System.arraycopy(sortedArray, 0, array, 0, array.length);
}

4. 성능 분석

public static void countingSort(int[] array) {
	// 입력 배열 내 최대값 구하기 : O(n)
    int max = Arrays.stream(array).max().getAsInt();
    
	// 보조 배열을 생성하여 각 값의 등장 횟수 기록 : O(n)
    int[] count = new int[max + 1];
    for (int number : array) {
    	count[number]++;
    }
    
    /**
	 * 배열 내 값의 누적 등장 횟수 계산 : O(k)
     *
     * k : 입력 배열의 최대값과 최소값의 차이
	 */
    for (int index = 1; index < count.length; index++) {
    	count[index] += count[index - 1];
    }
    
    // 정렬된 결과를 저장할 배열 생성
    int[] sortedArray = new int[array.length];
    
    // 입력 배열을 역순으로 순회하면서 정렬된 결과를 저장 : O(n)
    for (int index = array.length - 1; index >=0; index--) {
    	int number = array[index];
        int sortedIndex = count[number] - 1;	// 현재 값이 정렬된 배열에서 위치해야 할 인덱스
        sortedArray[sortedIndex] = number;
        count[number]--;	// 동일한 값에 대해 정렬된 위치가 변경되었기 때문에 누적 등장 횟수 감소
    }
    
    // 정렬된 배열을 입력 배열에 복사 : O(n)
    System.arraycopy(sortedArray, 0, array, 0, array.length);
}

O(n + n + k + n) = O(3n + k) → O(n+k)

∴ 시간복잡도 : O(n) (단, 입력값의 범위 k가 데이터의 개수 n에 비례하는 경우. 즉, k=O(n))

5. 특징

• 각 값이 등장한 횟수를 세어 정렬하므로 비교 기반 정렬 알고리즘들에 비해 빠른 속도를 보장한다.
• 입력값의 범위가 데이터의 개수보다 작거나 비례할 때 유용하다.
• 안정적 정렬 알고리즘이다.
  • 입력 배열의 오른쪽 원소부터 뽑아서 결과 배열의 오른쪽에서부터 저장하게 되므로, 정렬 전의 상대적 순서가 정렬된 상태에서도 그대로 유지된다.
• 제자리 정렬 알고리즘이 아니다.
  • 입력 배열 외에 보조 배열과 결과 배열이 별도로 필요하다.
• 보편적이지 못한 방법이다.
  • 효과적으로 사용하기 위해서는 다음과 같은 조건이 필요하기 때문
    1. 입력값의 작은 범위를 미리 알고 있어야 함
    2. 입력값의 출현횟수의 누적값과 정렬 결과를 저장하기 위한 배열이 추가적으로 필요함

📖 참고

• 이관용, 김진욱(2024). 알고리즘. 한국방송통신대학교출판문화원