Counting Sort : 계수 정렬

http://bowbowbow.tistory.com/8

Counting Sort

• Counting Sort
  • 소개
  • 정렬 과정
  • 애니메이션 예시
  • 구현
  • 정리
  • 끝

소개

Counting Sort는 정렬 알고리즘으로 의 시간복잡도를 갖습니다. 반면 일반적 상황에서 가장 빠른 정렬 알고리즘인 Quick Sort의 시간복잡도 입니다.

Counting Sort는 어떻게 이렇게 빠를까요? 그럼 왜 대부분의 정렬이 필요한 상황에서 더 빠른 Counting Sort를 안 쓰고 Quick Sort를 쓸까요?

Counting Sort가 어떻게 작동하는지 이해하고 나면 위 의문에 대한 답을 스스로 할 수 있을 겁니다!

정렬 과정

다음과 같은 수열 A를 정렬 해야하는 상황을 생각해봅시다.

위 수열을 정렬하면 아래와 같은 수열 B를 얻습니다.

Counting Sort가 어떻게 수열 A를 정렬해서 수열 B를 얻는지 따라가 봅시다.

1. 첫번째로 각 숫자가 몇번 등장하는지 세어줍니다.

숫자	0	1	2	3	4	5
등장 횟수	3	2	2	3	3	3

벌써 Counting Sort의 이름에 왜 Counting이 들어가있는지 알것 같지 않나요? 이렇게 각 숫자가 몇번 등장했는지 세어주기 때문입니다.

cf) 이 예제만 보면 1번 과정만 하고 벌써 정렬을 다 한 것 같습니다. 각 숫자가 등장한 횟수만큼 작은 순서대로 찍어주면 되기 때문이죠. 그럼 왜 굳이 아래 과정을 할까요?

 같은 수열을 정렬하는 상황을 생각해보세요. 중간에 등장한 뜬금없이 큰 100이 있어서 3~99까지 무의미한 순회를 해야하죠. 따라서 방금 생각한 방법은 숫자 크기에 시간복잡도가 매우 큰 영향을 받으므로 비효율적이라는 것을 알 수 있습니다.

2. 등장 횟수를 누적합으로 바꿔줍니다.

숫자	0	1	2	3	4	5
누적 합	3 (3)	5 (3+2)	7 (3+2+2)	10 (3+2+2+3)	13 (3+2+2+3+3)	16 (3+2+2+3+3+3)

이 누적합에서 알 수 있는 것은 숫자 0은 1 ~ 3인덱스에 위치하고 숫자 2는 4 ~ 7 인덱스에 위치한다는 것입니다.

3. 정렬할 배열 A를 뒤에서 앞으로 순회 하면서 정렬된 배열 B 에 넣어줍니다. 2번 과정에서 구한 누적합이 배열 A의 숫자가 배열 B의 어디에 위치해야 할지 정확하게 알려줍니다. 아래 5장의 이미지는 3번의 진행 과정을 설명합니다.

---

---

애니메이션 예시

예시 전체를 그림을 만드는건 힘들어서.. 누군가 멋지게 만들어주신 Counting Sort 애니메이션 링크를 첨부합니다. 아래 링크에서 Counting Sort 알고리즘 진행 과정 전체 예시를 볼 수 있습니다. 
http://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

구현

원래 배열을 A, 정렬된 배열을 B, 각 숫자가 몇개인지 세어준 배열을 count, 숫자 개수의 누적합을 담은 배열을 countSum이라 이름지었습니다.

	#include <cstdio>
	#define MAX_SIZE 1000
	#define MAX_NUM 10000
	int main(){
	int N, A[MAX_SIZE+1], B[MAX_SIZE+1], count[MAX_NUM+1], countSum[MAX_NUM+1];
	//수열의 길이 N은 MAX_SIZE이하여야합니다.
	scanf("%d", &N);
	//count배열을 모두 0으로 초기화
	for(int i = 0; i<= N ; i++)
	count[i] = 0;
	//수열 A에 입력되는 수는 MAX_NUM 이하여야합니다.
	for(int i =1 ; i<= N ; i++){
	scanf("%d", &A[i]);
	//숫자 등장 횟수 세기
	count[A[i]]++;
	}
	//누적합 구성
	countSum[0] = count[0];
	for(int i = 1 ; i<= MAX_NUM ; i++)
	countSum[i] = countSum[i-1]+count[i];
	//뒤에서 부터 수열 A 순회한다.
	for(int i = N ; i >= 1; i--){
	B[countSum[A[i]]] = A[i];
	countSum[A[i]]--;
	}
	//수열 A를 정렬한 결과인 수열 B를 출력한다.
	for(int i =1 ; i<= N ; i++)
	printf("%d ", B[i]);
	}

view rawcounting_sort.cpp hosted with ❤ by GitHub

아래 코드는 파이썬 버전입니다.

	#-*- coding: utf-8 -*-
	#한글 주석을 위해 인코딩 형식 utf-8을 선언함
	#counting sort python3 version
	#python3 문법으로 작성되었습니다.
	#입력 예시 : 1 3 17 5 7
	#출력 예시 : 1 3 5 7 17
	#입력될 수 있는 숫자의 최대 크기를 의미합니다.
	MAX_NUM = 1000
	#A는 입력된 숫자를 저장하는 배열
	A = list(map(int, input().split()))
	#N은 입력된 숫자의 개수 입니다.
	N = len(A)
	#0으로 초기화된 입력될 MAX_NUM+1 길이의 배열 count를 생성합니다.
	count =[0]*(MAX_NUM+1)
	#countSum은 누적합을 저장하는 배열입니다.
	countSum =[0]*(MAX_NUM+1)
	#숫자 등장 횟수 세기
	for i in range(0, N):
	count[A[i]] += 1
	#숫자 등장 횟수 누적합 구하기
	countSum[0] = count[0]
	for i in range(1, MAX_NUM+1):
	countSum[i] = countSum[i-1]+count[i];
	#B는 정렬된 결과를 저장하는 배열
	B = [0]*(N+1)
	for i in range(N-1, -1, -1):
	B[countSum[A[i]]] = A[i]
	countSum[A[i]] -= 1
	#수열 A를 정렬한 결과인 수열 B를 출력한다.
	result = ""
	for i in range(1, N+1):
	result += str(B[i]) + " "
	print(result)

view rawconting_sort.py hosted with ❤ by GitHub

정리

알고리즘의 진행과정을 따라가보면서 처음 소개에서 했던 의문들에 대한 답을 얻을 수 있었을 겁니다.

Counting Sort 알고리즘의 시간복잡도는 O(n) 으로 Quick Sort보다 훨씬 유리해보입니다. 그러나 세상에 공짜는 없다는 말처럼 Counting Sort는 대부분의 상황에서 엄청난 메모리 낭비를 야기할 수 있습니다.

누적합 배열에 대한 접근을 O(1)에 달성하기 위해 정렬할 배열에 포함된 숫자의 최댓값 만큼의 메모리를 필요로 합니다. 아까 추가로 예시든  배열에 Counting Sort 알고리즘으로 정렬하기 위해서는 누적합 배열의 길이를 100으로 잡는 낭비를 해야합니다. 만약 배열에 최댓값으로 10억이 포함되어 있다면 엄청난 낭비가 되겠죠.

따라서 Counting Sort는 위에서든 예시처럼 

정렬하는 숫자가 특정한 범위(위 예시 : 0~5) 안에 있을 때 사용하게 됩니다.

Counting Sort를 대표적으로 활용하는 사례는 26개의 알파벳으로 이루어진 문자열에서 Suffix Array를 얻는 경우인데 이때 Counting Sort를 사용하기 때문에 일반적인 Sort를 사용해서 Suffix Array를 얻때 시간복잡도 보다 빠른 에 Suffix Array를 얻는 것이 가능합니다.

끝