카운팅 정렬(Counting Sort)

[정렬 방법]

정렬에 앞서, 이 정렬을 이용하고자 할 때 조건은 정해진 범위 내의 숫자들만을 배열의 원소값으로 가져야 한다는 것이다. 이렇기에 나중에 타 정렬들과 비교했을 때 상대적으로 시간 복잡도가 작고 빠른 특성을 띤다.

먼저, 임의의 배열 arr에 정해진 범위의 숫자들(ex)0~20)을 넣는다. 이후 20 크기의 배열 c_arr을 만들고 arr을 for문을 돌리면서 원소값과 같은 index의 c_arr의 값을 1씩 증가시킨다. 이후 결과로 사용할 result 배열에 arr의 값들을 정렬시킬 것인데, arr의 가장 마지막 원소값(k)부터 시작해서 그 원소값과 같은 인덱스의 c_arr의 원소값과 같은 인덱스의 result 배열의 원소값에 k를 넣는다. 이 과정을 거치면 사용된 c_arr의 원소값을 -1하고 arr의 값 또한 그 왼쪽의 값으로 이동하여 같은 과정을 거친다.

---

[정렬 과정]

n 크기의 임의의 배열 arr에 정해진 범위의 숫자들(ex)0~k)을 입력한다.

 

이후, 정해진 범위의 숫자 크기(0~k이므로 k+1)의 배열 c_arr을 만드는데 이 배열은 arr에 있는 값들의 개수를 저장하는 배열이다.

 

for문을 통해 arr[0]~arr[n-1]까지의 값들을 확인하며 그 값과 같은 인덱스의 c_arr 원소값을 +1한다.

이후, c_arr을 누적형태로 바꾸어나간다.

ex) 0, 1, 1, 3, 2  -> 0, 1, 2, 5, 7

코드로 표현하자면, for i <- 0 to k-1 { c_arr[i+1] += c_arr[i];

이후, 정렬된 arr의 값들을 적어둘 arr과 같은 크기의 배열 result를 만든다.

 

<1단계>

arr[n-1]과 같은 인덱스의 c_arr의 원소값과 같은 인덱스의 result의 원소에 arr[n-1] 값을 입력한 후, c_arr의 원소값은 1 감소시킨다.

코드로 표현하자면,

result[ c_arr[ arr[n-1] ]-1 ] = arr[n-1];

c_arr[ arr[n-1] ]--;

 

<2단계>

 

arr[n-2]과 같은 인덱스의 c_arr의 원소값과 같은 인덱스의 result의 원소에 arr[n-2] 값을 입력한다.

코드로 표현하자면, result[ c_arr[ arr[n-2] ]-1 ] = arr[n-2];

c_arr[ arr[n-2] ]--;

 

.

.

.

 

<n단계>

 

arr[0]과 같은 인덱스의 c_arr의 원소값과 같은 인덱스의 result의 원소에 arr[0] 값을 입력한다.

코드로 표현하자면, result[ c_arr[ arr[0] ]-1 ] = arr[0];

c_arr[ arr[0] ]--;

 

이 과정이 모두 끝나면 arr에 중복되어 들어가 있는 숫자들이 result에 정렬이 된다.

 

---

[pseudo code]

CountingSort(arr, result, k) //정렬할 배열 arr과 정렬될 공간인 result 배열, 정해진 범위의 숫자
for i <- 0 to k
  do c_arr[i] <- 0 //c_arr배열의 element들을 모두 0으로 초기화시킨다.
for j <- 0 to length[arr]-1
  do c_arr[arr[j]] <- c_arr[arr[j]] + 1 //arr에 있는 원소값과 같은 인덱스의 c_arr 원소값들을 1씩 증가시킨다. 
for i <- 0 to k-1
  do c_arr[i] <- c_arr[i] + c_arr[i-1] //이후 c_arr의 값들을 작은 인덱스의 원소값들부터 누적한 값으로 변경한다.
for j <- length[c_arr]-1 downto 0
  do result[c_arr[arr[j]]-1] <- arr[j] //arr배열의 끝부터 왼쪽방향으로 해서 result값에 정렬시켜나간다.
    c_arr[arr[j]] <- c_arr[arr[j]] - 1 //값을 집어넣은 후에는 해당 인덱스의 c_arr 원소값을 1 감소한다.

---

[코드 구현]

 

public class CountingSort {
  
    public static void main(String[] args) {
        int[] arr = {22, 5, 34, 1, 32, 18, 50, 8}; //예시로 작성한 배열
        StringBuilder sb = new StringBuilder();
        int [] result = new int [arr.length];
      
      countingSort(arr, result, 50);
      for (int a : result) {
        sb.append(a);
        sb.append(" ");
      }
      System.out.println(sb);
    }
  
    private static void countingSort(int[] arr, int[] result, int k) {
        int[] c_arr = new int[k+1];
        for(int i=0; i <=arr.length-1; i++){
            c_arr[arr[i]]++;
        }
        
        for(int i=0; i <k; i++){
            c_arr[i+1] += c_arr[i];
        }

        for(int i=arr.length-1; i>=0; i--){
            result[c_arr[arr[i]]-1] = arr[i];
            c_arr[arr[i]]--;
        }
    }
}

 

---

[시간 복잡도]

countingSort로 들어오기 전 arr배열을 입력받으면 그 길이가 n이므로 T(n)이고, 

countingSort 함수 안에서 T(n) + T(k) + T(n)이므로 시간 복잡도는 O(n+k)이다.

이때, k = O(n)이라면 시간복잡도는 O(n)이지만, 터무니없이 커지거나 더 크다면 시간복잡도는 더 커진다.

그래서 k가 클 경우에는 실용적이지 못하다.

 

또한, 카운팅 정렬은 입력받은 숫자들 중 동일한 값들이 있을 때 FIFO구조 성질을 만족하므로 stable 정렬 알고리즘이다.