Counting sort(계수 정렬)

계수정렬에는 세개의 배열이 필요하다.

우선 정렬해야할 수들을 담은 array1

최대 값을 기준으로 숫자들의 누적합을 담을 array2

마지막으로 정렬된 수를 담을 array3이다.

예를들어 최대 값이 5라면 array2에는 0부터 5까지 index를 이용해 6가지 수의 개수를 표현할 수 있다.

array1을 [4,1,0,1,1,2,1,2]라고 하자.

우선 array2를 누적합이 아닌 index를 숫자로, value를 개수로 생각하면 [1,4,2,0,1,0]인 배열이 된다.

이를 누적합으로 표현하면 [1,5,7,7,8,8]로 나타낼 수 있다.

누적합은 0번째 index에서 시작하여 이전 index와의 합으로 누적합을 구한다.

마지막으로 array3에 정렬된 수를 넣기 위한 작업이 있다.

array1의 맨 우측부터 시작해서 array2의 index가 2의 값은 7인데 7에서 1을빼 6으로 만들고 7번째(idx6)의 자리에 넣는다.

이와 같은 방식으로 array2를 수정하면서, array1의 첫번째 값까지 위치를 잡으면

[0,1,1,1,1,2,2,4]라는 array3이 완성된다.

counting sort는 O(n+k) (k는 최대 값)의 시간복잡도를 가진다.

최대값이 매우커져 2000000이런 식이라면 k가 매우 커지기 때문에 비효율적인데,

최소값을 뺀 수부터 계산을 시작하는 방식으로 보완할 수 있다.

백준 정렬3 문제를 풀다가 제한된 메모리 안에 문제를 풀어야 하는 제약조건 때문에 계수정렬을 공부했다.

파이썬에서는 hash table로 구현한 dictionary를 이용해 계수정렬처럼 key와 value로 숫자와 개수를 표현할 수 있다.

이는 개수가 0인 값을 필요로 하지 않는다.