[알고리즘] 계수정렬

간만에 하는 블로깅이다.
블로그를 꾸준히 써야한다는 건 머리로는 알고 있는데, 막상 일에 치이다보면 어느새 까먹곤 한다. 🥲

계수정렬이란?

계수정렬은 Count Sorting이라 불리는 알고리즘이다.
그 이유는 배열 내에 있는 데이터들의 개수를 세서, 별도의 인덱싱 배열에 카운팅을 해두고 그 카운팅된 수를 기반으로 조건에 따라 출력하기 때문이다.

퀵, 병렬, 힙 정렬보다 빠른 알고리즘으로 볼 수 있지만, 단순히 개수를 세는 방식이기 때문에 데이터의 케이스가 너무 다양한 경우에는 오히려 효율이 떨어지는 정렬 알고리즘이라고 볼 수 있다.
즉, 데이터 케이스가 다양하지 않은 경우에만 적용해야 효과적인 알고리즘이라고 보면 된다.

시간복잡도

• O(N)

구현방법

• 나동빈님의 알고리즘 강의를 통해 공부하고 있어서, C로 작성된 코드를 별도로 Java와 Python을 이용해 구현해보겠다.
• 아래는 C로 구현한 코드

#include <stdio.h>

int main(void) {
	int count[5];
	int array[20] = {
		1, 3, 2, 4, 3, 2, 3, 4, 5, 2, 1, 2, 3, 4, 4, 5, 2, 3, 1, 5
	};
		
	for(int i = 0; i < 5 ; i++) {
		count[i] = 0;
	}
	
	for(int i = 0; i < 20; 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 (편의상 main 메소드만)

public static void main(String args) {
	int[] count = new int[5];
	int[] array = {
		1, 3, 2, 4, 3, 2, 3, 4, 5, 2, 1, 2, 3, 4, 4, 5, 2, 3, 1, 5
	}
	
	for(int i = 0; i < count.length(); i++) {
		count[i] = 0;
	}
	
	for(int i = 0; i < array.length(); i++) {
		count[array[i] - 1]++;
	}
	
	for(int i = 0; i < count.length(); i++) {
		if(count[i] != 0) {
			for(int j = 0; j < count[i]; j++) {
				system.out.printf("%d", i + 1);
			}
		}
	}
}

• Python

count=[0] * 5
array=[1, 3, 2, 4, 3, 2, 3, 4, 5, 2, 1, 2, 3, 4, 4, 5, 2, 3, 1, 5]

for i in range(len(array)):
    count[array[i] - 1] += 1

for i in range(len(count)):
    if(count[i] != 0):
        for j in range(count[i]):
            print(i + 1, end="")

대충 잘 되는 것 같다.
나중에 해당 정렬을 활용해서 문제나 한 번 풀어봐야지.