티스토리 뷰
소개
Counting Sort는 정렬 알고리즘으로 
Quick Sort의 평균시간복잡도는 
Counting Sort는 어떻게 이렇게 빠를까요? 그럼 왜 대부분의 정렬이 필요한 상황에서 더 빠른 Counting Sort를 안 쓰고 Quick Sort를 쓸까요?
Counting Sort가 어떻게 작동하는지 이해하고 나면 위 의문에 대한 답을 스스로 할 수 있을 겁니다!
정렬 과정
다음과 같은 수열 A를 정렬 해야하는 상황을 생각해봅시다.
위 수열을 정렬하면 아래와 같은 수열 B를 얻습니다.
Counting Sort가 어떻게 수열 A를 정렬해서 수열 B를 얻는지 따라가 봅시다.
- 첫번째로 각 숫자가 몇번 등장하는지 세어줍니다.
| 숫자 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 등장 횟수 | 3 | 2 | 2 | 3 | 3 | 3 |
벌써 Counting Sort의 이름에 왜 Counting이 들어가있는지 알것 같지 않나요? 이렇게 각 숫자가 몇번 등장했는지 세어주기 때문입니다.
cf) 이 예제만 보면 1번 과정만 하고 벌써 정렬을 다 한 것 같습니다. 각 숫자가 등장한 횟수만큼 작은 순서대로 찍어주면 되기 때문이죠. 그럼 왜 굳이 아래 과정을 할까요?
같은 수열을 정렬하는 상황을 생각해보세요. 중간에 등장한 뜬금없이 큰 100이 있어서 3~99까지 무의미한 순회를 해야하죠. 따라서 방금 생각한 방법은
숫자 크기에 시간복잡도가 매우 큰 영향을 받으므로비효율적이라는 것을 알 수 있습니다.
- 등장 횟수를 누적합으로 바꿔줍니다.
| 숫자 | 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 인덱스에 위치한다는 것입니다.
정렬할 배열 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이라 이름지었습니다.
아래 코드는 파이썬 버전입니다.
정리
알고리즘의 진행과정을 따라가보면서 처음 소개에서 했던 의문들에 대한 답을 얻을 수 있었을 겁니다.
Counting Sort 알고리즘의 시간복잡도는 O(n) 으로 Quick Sort보다 훨씬 유리해보입니다. 그러나 세상에 공짜는 없다는 말처럼 Counting Sort는 대부분의 상황에서 엄청난 메모리 낭비를 야기할 수 있습니다.
누적합 배열에 대한 접근을 O(1)에 달성하기 위해 정렬할 배열에 포함된 숫자의 최댓값 만큼의 메모리를 필요로 합니다. 아까 추가로 예시든 
따라서 Counting Sort는 위에서든 예시처럼
특정한 범위(위 예시 : 0~5) 안에 있을 때 사용하게 됩니다.Counting Sort를 대표적으로 활용하는 사례는 26개의 알파벳으로 이루어진 문자열에서 Suffix Array를 얻는 경우인데 이때 Counting Sort를 사용하기 때문에 일반적인 Sort를 사용해서 Suffix Array를 얻때 시간복잡도 
끝
글에 오류나
Counting Sort에 대한 질문이 있으면 댓글로 남겨주세요!
- Total
- Today
- Yesterday