Count sort

알고리즘/자료구조 2016. 7. 23. 19:47 Posted by 아는 개발자

quicksort나 mergesort처럼 일반적인 sorting알고리즘은 O(NlogN)을 가지나 sorting에 사용되는 값들을 사전에 알고 있는 경우에는 시간복잡도를 O(N)까지 단축 시킬 수 있다. 그중에서도 가장 강력하게 사용되는 알고리즘이 Count sorting이다.


Count sorting은 정렬에 쓰이는 값이 충분히 작은 경우(배열의 최대 크기가 될 수 있는 값보다 작아야 한다)에 주로 사용할 수 있다. 배열의 인덱스는 이미 자동적으로 정렬되있으니 수열에 포함된 값 각각의 개수를 배열의 인덱스에 해당하는 값에 저장해둔 후 그 그 개수를 참고해서 정렬하는 방식이다.


글로 설명하기에는 어려우니 예를 들어보자. 


5 3 6 7 4 5 인 수열을 정렬한다고 하자. 위 수열의 각 값의 개수를 관리하는 배열을 count[10]라 하자. 그러면 count의 값은 다음과 같을 것이다.


count[0] = 0

count[1] = 0

count[2] = 0

count[3] = 1

count[4] = 1

count[5] = 2

count[6] = 1

count[7] = 1

count[8] = 0

count[9] = 0


정렬하고자한 수열의 값들은 이미 배열의 index를 통해서 자동적으로 정렬이 되었다. 이제 각각의 개수만큼 표현만 해주면 된다.


count[0] = 0 -> 수열에 포함 안됨

count[1] = 0 -> 수열에 포함 안됨

count[2] = 0 -> 수열에 포함 안됨

count[3] = 1 -> 3

count[4] = 1 -> 3, 4

count[5] = 2 -> 3, 4, 5, 5

count[6] = 1 -> 3, 4, 5, 5, 6

count[7] = 1 -> 3, 4, 5, 5, 6, 7

count[8] = 0 -> 수열에 포함 안됨

count[9] = 0 -> 수열에 포함 안됨


생각해보면 정말 자명하고 직관적이어서 쉽다. 구현도 쉬워서 자주자주 써먹을 수 있을 것 같으나 써야할 때를 자주 깜빡한다.


가장 최근에 푼 문제중에는 좌표상에 표현되는 값을 x, y로 정렬해야 했는데 조건이 x, y < 1000000이었다. 이때도 count sort를 사용해서 정렬 할 수 있었는데 구현도 어려운 quicksort를 구현하느라 시간을 한참 소비했다 ㅡㅡ


다른분이 정렬한 코드를 참고해서 새롭게 작성한 후 올린다..




'알고리즘 > 자료구조' 카테고리의 다른 글

완전순열(교란순열)  (0) 2016.12.04
LCA(Lowest Common Ancestor)  (0) 2016.07.30
Count sort  (0) 2016.07.23
Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05
LIS를 O(nlogn)시간 내에 해결하는 방법  (0) 2015.08.27