Count sort

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를 구현하느라 시간을 한참 소비했다 ㅡㅡ

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

// sortIdx는 해당 값의 시작 위치를 설정한다... for (i = 1; i <= N; i++) { sortIdx[node[i].pos[1] + 1]++; } prev = sortIdx[srcY]; // 더해주면서 해당 위치에 존재해야하는 값들은 뒤로 밀려주는 방법... for (i = srcY + 1; i <= dstY; i++) { sortIdx[i] += prev; prev = sortIdx[i]; } // y에 대해서 먼저 정렬해주는 방법. for (i = 1; i <= N; i++) { idx = sortIdx[node[i].pos[1]]++; midPoint[idx] = node[i]; } for (i = srcX; i <= dstX; i++) sortIdx[i] = 0; // 다음것의 시작 위치를 밀려주는 방법.... for (i = 0; i < numberOfPoints; i++) sortIdx[midPoint[i].pos[0] + 1]++; prev = sortIdx[srcX]; for (i = srcX; i <= dstX; i++) { sortIdx[i] += prev; prev = sortIdx[i]; } // 다음값의 시작위치를 밀어주면서 새롭게 값을 만들 수 있다 for (i = 0; i < numberOfPoints; i++) { idx = sortIdx[midPoint[i].pos[0]]++; node[idx] = midPoint[i]; }