[자료구조/C, Java] 계수 정렬(Counting Sort)

 

https://www.youtube.com/watch?v=n4kbFRn2z9M

목소리가 특이하신 분...ㅎ

 

범위 조건이 있는 경우에 한해서 굉장히 빠른 알고리즘이 있다.

계수 정렬(Counting Sort)는 단순하게 '크기를 기준으로 개수를 세는' 알고리즘이다.

지금까지는 모든 데이터를 그 자체로 위치를 바꾸어가며 정렬하는 알고리즘이었다. 계수 정렬은 '크기를 기준'으로 갯수만 세주면 되기 때문에 위치를 바꿀 필요가 없다. 모든 데이터에 한 번씩만 접근하면 된다는 점에서 무척이나 효율적이다.

 

1. 결과 배열의 크기를 숫자의 크기 범위만큼 잡아준다.

2. 하나를 확인할 때마다 배열에 데이터를 한개씩 증가시켜준다.

3. 출력할 때는 단순하게 배열 원소의 숫자만큼 반복하면 된다.

- 시간 복잡도 : O(N)

 

C언어 코드

#include <stdio.h>

int main(void){
	int temp;
    int count[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<5; i++){
    	count[i] = 0;
    }
    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);
            }
        }
    }
    return 0;
}

 

Java 코드

public class Test{
	public static void main(String[] args){
    	int[] array = {
    	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
    	};
        int temp ;
        int count[5];
        
        for(int i=0; i<5; i++){
          count[i] = 0;
      }
      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);
              }
          }
      }
    }
}