알고리즘 [Algorithm] - 계수 정렬 Counting Sort (7) (C, Python)

계수 정렬

  이번에는 계수 정렬에 대해 알아보자. 계수 정렬이란 단순하게 '크기를 기준으로 세는 알고리즘'이다. 하지만 계수 정렬은 '범위조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘이다.

 

 지금까지 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬을 배웠는데 지금 까지 배운 정렬 중 가장 빠른 정렬방법을 고르라면 시간 복잡도 O(N*log N)을 가지는 퀵 정렬, 병합 정렬, 힙 정렬 중 하나를 고를 것이다. 하지만 이보다 더 빠르게 정렬해야 한다면 어떻게 해야될까?

 

  계수 정렬은 범위가 주어져있다면 시간복잡도 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

---

 

#include <stdio.h>

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

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

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

위와 같이 소스코드도 굉장히 간결하다.

파이썬

data = [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]
count=[0,0,0,0,0,0]
for i in range(len(data)):
  count[data[i]] +=1

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

 

---

이 글은 나동빈님의 실전 알고리즘 강좌 (Algorithm Programming Tutorial)를 참고해 작성하였습니다.

https://www.youtube.com/watch?v=qQ5iLNjpxSk&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz