계수 정렬 ( Counting Sort )

계수 정렬

• '범위 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘 -> 속도 : O(N)
• 단순하게 '크기를 기준'으로 세는 알고리즘

 

문제) 주어진 5 이하 자연수 데이터들을 오름차순 정렬하시오.
     1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

• 크기를 기준으로 갯수만 세주면 되기 때문에 다른 정렬들처럼 위치를 바꿀 필요가 없다.
• 모든 데이터에 한 번씩만 접근하면 된다는 점에서 매우 효율적이다.

 

초기 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
0	0	0	0	0

 

1. 첫번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
1	0	0	0	0

 

2. 두번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
1	0	1	0	0

 

3. 세번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
1	1	1	0	0

 

 

4. 네번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
1	1	1	1	0

 

5. 다섯번째 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
1	1	2	1	0

 

.  .  . ( 위와 같이 계속 반복 )

 

 

최종 상태

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 1 1 1

크기 = 1	크기 = 2	크기 = 3	크기 = 4	크기 = 5
8	6	8	4	4

- 이제 크기 1부터 5까지 해당 숫자만큼 순서대로 출력하면 된다. 

- 이게 바로 '크기를 기준'으로 정렬하는 계수정렬의 정렬 방법이다.

 

 

계수 정렬 구현 코드

#include<stdio.h>

int main(){
  int temp;
  int count[5] = {0,}; // 범위가 5이하이기 때문에 5개까지 들어갈 공간을 만들어줌
  int array[30] = {
    1,3,2,4,3,2,5,3,1,2,
    3,4,4,3,5,1,2,3,5,2,
    3,1,4,3,5,1,2,1,1,1
  };

  for(int i = 0; i < 30; i++){
    count[array[i] - 1]++;
  }

  for(int i = 0; i < 5; i++){
    if(count[i] != 0){
      for(int j = 0; j < count[i]; j++){
        printf("%d", i + 1);
      }
    }
  }
}

- count[]를 문제에 주어진 수의 범위만큼 생성해줘야 한다.

  만약 주어진 숫자 중에 10000이 있다면 count[]도 10000까지 잡아줘야 한다.
  그렇기 때문에 보통의 상황에 자주 쓸 수 있는 알고리즘은 아니다.
  -> 정렬할 데이터의 범위에 영향을 매우 크게 받는 정렬 알고리즘이다.