계수 정렬 (Counting Sort)

정렬 알고리즘

 

 

계수 정렬 (Counting Sort)

계수 정렬은 요소들을 직접 비교하지 않고 정렬하는 알고리즘으로 정수 정렬 알고리즘 중 하나입니다.

배열의 각각의 요소들의 수를 센 다음 조건에 맞춰 수를 배열하는 정렬하는 방식입니다. 원소들의 값이 특정 범위 내에 있을 때 효율적으로 작동할 수 있습니다. 

 

시간 복잡도 : O(n + k)  n : 배열의 크기, k : 가장 큰 수 

 

 

장점 

• 시간 복잡도가 빠를 수 있다. 특정한 상황에서는 비교 기반 정렬 방법보다 빠를 수 있습니다.
• 안정적인 정렬이다. 동일한 값을 가진 원소들의 상대적 순서가 유지됩니다.

 

단점

• 공간 복잡도가 높다. 추가적인 공간이 필요하기 때문이다. (카운트 배열과 정렬된 배열)
• 제한 조건 : 원소들이 정수여야 하며 작은 범위여야 효과적이다. 

계수 정렬을 사용하려면 정수여야 하면 작은 범위의 데이터셋에서는 효율적입니다. 하지만 정수가 아니면 사용할 수 없고 범위가 큰 데이터셋에서는 비효율적입니다. 

계수 정렬은 이후에 기수 정렬(Radix)에서 사용되기도 합니다. 

 

 

 

동작 과정

예시 배열 

[4, 2, 2, 8, 3, 3, 1]

 

 

1. 최댓값확인

배열에서 최댓값을 확인합니다. 

max : 8 

 

2. 계수 배열(count 배열) 생성

최댓값 크기에 해당하는 계수 배열을 생성합니다. 계수 배열에는 원래 배열의 요소들의 갯수를 기록합니다. 

계수 배열(초기화) : [0, 0, 0, 0, 0, 0, 0,]

 

3. 배열의 각 요소 세기 

입력 배열을 순회하며 각 숫자의 개수를 계수 배열에 저장합니다.

계수 배열 : [0, 1, 2, 2, 1, 0, 0, 0, 1]

 

4. 계수 배열의 누적합 계산 

계수 배열로 누적합을 계산합니다. 이를 통해 각 요소가 정렬된 배열에서 시작할 위치를 나타냅니다. 

누적합 배열 : [1, 3, 5, 6, 6, 6, 7] 

 

5. 정렬된 배열 생성 

원래 배열을 역으로 순회하면서 누적합 배열을 통해 각 요소의 시작 위치에 배치합니다. 누적합 배열에서 해당 숫자의 위치를 찾고 숫자를 배치한 후 그 위치를 감소하여 같은 요소의 시작 위치를 업데이트 합니다. 이런 식으로 정렬을 합니다. 

정렬된 배열 : [1, 2, 2, 3, 3, 4, 8]

 

 

 

동작 예시

원본 배열 : [4, 2, 2, 8, 3, 3, 1]

누적합 배열 : [1, 3, 5, 6, 6, 6, 7] 

원본 배열을 역으로 순회하면서 각 원소들의 올바른 위치로 가게 하여 정렬합니다. 

(여기서는 1부터 셉니다. 하지만 코딩을 할 때는 0부터는 시작하니 count[array[i]] - 1 을 하여 배열에 맞게 바꿉니다. )

 

원본 배열 7위치인 1부터 시작합니다. 누적합을 보면 1의 시작 위치는 1입니다. 결과 배열 1위치에 1을 두고 누적합 배열 1을 감소합니다. 

 

누적합 배열 : [0, 3, 5, 6, 6, 6, 7]

정렬된 배열 : [1, 0, 0, 0, 0, 0, 0]

 

 

 

다음은 원본 배열 5위치인 3입니다. 누적합을 보면 3의 시작 위치는 5입니다. 결과 배열 5위치에 3을 두고 누적합 배열 3을 1 감소합니다.

 

누적합 배열 : [0, 3, 4, 5, 6, 6, 6, 7]

정렬된 배열 : [1, 0, 0, 0, 3, 0, 0]

 

 

 

다음은 원본 배열 5위치인 3입니다. 누적합을 보면 3의 시작 위치는 전 작업으로 인해 하나 감소된 4입니다. 결과 배열 4위치에 3을 두고 누적합 배열 3을 1 감소합니다. 

 

누적합 배열 : [0, 3, 3, 5, 6, 6, 6, 7]

정렬된 배열 : [1, 0, 0, 3, 3, 0, 0]

 

 

 

다음은 원본 배열 4위치인 8입니다. 누적합을 보면 8의 시작 위치는 7입니다. 결과 배열 7위치에 8을 두고 누적합 배열 8을 1 감소합니다.

 

누적합 배열 : [0, 3, 3, 5, 6, 6, 6, 6]

정렬된 배열 : [1, 0, 0, 3, 3, 0, 8]

 

 

 

다음은 원본 배열 3위치인 2입니다. 누적합을 보면 2의 시작 위치는 3입니다. 결과 배열 3위치에 2를 두고 누적합 배열 2에 1을 감소합니다.

 

누적합 배열 : [0, 2, 3, 5, 6, 6, 6, 6]

정렬된 배열 : [1, 0, 2, 3, 3, 0, 8]

 

 

 

다음은 원본 배열 2위치인 2입니다. 누적합을 보면 2의 시작 위치는 2입니다. 결과 배열 2위치에 2를 두고 누적합 배열2에 1을 감소합니다. 

 

누적합 배열 : [0, 1, 3, 5, 6, 6, 6, 6]

정렬된 배열 : [1, 2, 2, 3, 3, 0, 8]

 

 

 

다음은 원본 배열 1위치인 4입니다. 누적합을 보면 4의 시작 위치는 5입니다. 결과 배열 5위치에 4를 두고 누적합 배열 4에 1을 감소합니다. 

 

누적합 배열 : [0, 1, 3, 5, 6, 6, 6, 6]

정렬된 배열 : [1, 2, 2, 3, 3, 4, 8]

 

 

 

 

 

Java 코드 구현

위의 과정을 Java 코드로 구현하면 다음과 같습니다.

/*
계수 정렬  Counting Sort
시간 복잡도 : O(n + k)

정수 배열에서만 사용 가능
정수의 개수를 센 다음 정렬
 */
public class CountingSort {

  public static void main(String[] args) {
    int[] array = {4, 2, 2, 8, 3, 3, 1};
    printArray(array);
    countingSort(array);
    printArray(array);
  }

  public static void countingSort(int[] array) {
    int n = array.length;

    // 최댓값 찾기
    int max = array[0];
    for(int i = 1; i < n; i++) {
      max = Math.max(max, array[i]);
    }

    // 계수 배열 초기화
    int[] count = new int[max+1];

    // 각 숫자 출현 횟수 세기
    for(int i = 0; i < n; i++) {
      count[array[i]]++;
    }

    // 계수 배열의 누적합 계산 - 시작 인덱스 표시, 안정적인 정렬(같은 요소가 있을 때, 순서 유지)
    for(int i = 1; i <= max; i++) {
      count[i] += count[i -1];
    }

    // 결과 배열 초기화
    int[] output = new int[n];

    // 원본 배열을 역순으로 순회하며 결과 배열에 정렬된 데이터 배치
    for(int i = n - 1; i >= 0; i--) {
      output[count[array[i]] - 1] = array[i];
      count[array[i]]--; // 요소의 시작 인덱스 조정
    }
    // count = {0, 1, 3, 5, 6, 6, 6, 7} 누적합의 요소는 시작 인덱스, 인덱스는 뒤에서부터 채워진다.
    // array = {4, 2, 2, 8, 3, 3, 1} 이면 1부터 탐색을 시작한다.
    // output[count[array[i]] - 1] 에서 i가 n-1이면 output[0] = 1 이 된다.
    // output = {1, 0, 0, 0, 0, 0, 0}
    // count[1]-- 이 되어 0이 된다.
    // count = {0, 0, 3, 5, 6, 6, 6, 7}

    // i = n-2이면 array[5] = 3이 된다.
    // output[count[3] - 1] = 3, count[3] - 1 은 5 - 1이므로 4이다. output[4] = 3이 된다.
    // output = {1, 0, 0, 0, 3, 0, 0}
    // count[3]-- 이 되어 4가 된다
    // count = {0, 0, 3, 4, 6, 6, 6, 7}

    // i = n-3이면 array[4] = 3이 된다.
    // output[count[3] - 1] = 3, count[3] - 1은 4 -1 이므로 3이다. output[3] = 3이 된다.
    // output = {1, 0, 0, 3, 3, 0, 0}
    // count[3]-- 이 되어 3이 된다.
    // count = {0, 0, 3, 3, 6, 6, 6, 7}

    // 이런 식으로 인덱스가 줄어들면서 뒤에서부터 정렬이 진행된다.


    // 결과 배열을 원본 배열에 복사
    System.arraycopy(output, 0, array, 0, n);

  }



  public static void printArray(int[] array) {
    for(int number : array) {
      System.out.print(number + " ");
    }
    System.out.println();
  }
}

 

 

 

 

마무리

이번에는 비교 없이 정수 배열을 정렬하는 계수 정렬에 대해 정리했습니다.

다음에는 자릿수로 정렬하는 기수 정렬에 대해 정리해 보겠습니다.

감사합니다.