이번에 알아볼 알고리즘은 sorting의 편법(?)이라고 할 수 있는 Counting sort에 대해서 알아보겠습니다. 보통 정렬을 하기 위해서는 두 원소를 집어서 비교를 해야 해서 이렇게 비교 방식으로 정렬하는 방법은 무조건 $O(n\log n)$ 이상이 필요하다는 정리가 있습니다. 하지만 이번에 알아볼 Counting sort는 비교하는 방식이 아니기 때문에 $O(k+n)$이라는 획기적인 속도를 낼 수 있습니다.(여기서 $k$는 list의 원소들의 값의 range 크기를 의미합니다.) 하지만 물론 공짜는 없겠죠? 제약조건이 반드시 따라붙게 되어있습니다.
영화의 별점을 정렬한다고 가정해 봅시다.(우리는 정수만 가정할 것입니다!!) 별점은 0점에서 5점까지 존재할 것이고, 예를들어 (1, 3, 2, 4)가 있다고 하면, 비교하지 않고 정렬하는 방법은 어떤 것이 있을까요? Bucket sort라는 방식은 min값과 max값을 알고있고, discrete한 원소들을 대상으로 나올 수 있는 모든 가능성에 대해 카운팅 하는 공간을 만들어 놓고 리스트를 쭉 돌면서 해당 원소를 count 한 뒤에 마지막으로 count한 숫자만큼씩 반복해서 넣어주는 방식입니다.
아까 예에서 (1, 3, 2, 4)의 경우, 별점은 0~5까지의 자연수이므로 (0, 0, 0, 0, 0, 0) 이렇게 count 리스트를 만든 후에, 1이 나왔으므로 (0, 1, 0, 0, 0, 0), 3이 나왔으므로 (0, 1, 0, 1, 0, 0), 2가 나왔으므로 (0, 1, 1, 1, 0, 0), 4가 나왔으므로 (0, 1, 1, 1, 1, 0)이런식으로 count를 하는 것입니다. 이 때 $O(n+k)$가 들겠죠?(이 경우엔 $k=6$입니다.) 마지막으로 count 리스트를 돌면서(이 count 리스트는 index자체가 이미 정렬되어 있기 때문에) 횟수만큼 출력해주면 정렬이 될 것입니다.
def countingSort(A, smallest, largest):
nbins = largest - smallest + 1 #이만큼의 공간안에 숫자들이 다 들어갈 것입니다.
bins = [0]*nbins #bins라는 공간에 할당해 놓고,
# 각 원소를 count합니다.
for i in A:
bins[i-smallest] += 1
#마지막으로 count된 횟수만큼씩 그대로 넣어주면 정렬이 될 것입니다.
index = 0
for i in range(nbins):
for j in range(bins[i]):
A[index] = i+smallest
index += 1그럼 이제 결과값이 잘 정렬되는지 확인해 보겠습니다.
>>> import random
>>> A = [random.randint(0, 100) for _ in range(10)] #0~100까지의 정수를 임의로 10개 발생시킴.
>>> print "원본 리스트: ", A
원본 리스트: [53, 46, 60, 87, 70, 74, 99, 68, 96, 90]
>>> print "정답: \t", sorted(A)
정답: [46, 53, 60, 68, 70, 74, 87, 90, 96, 99]
>>> countingSort(A, 0, 100)
>>> print "우리정답: ", A
우리정답: [46, 53, 60, 68, 70, 74, 87, 90, 96, 99]잘 정렬되었음을 확인하실 수 있죠? 물론 편법이긴 하지만, 그래도 필요에 따라서는 굉장히 효율적인 방법이니까 뇌를 유연하게 움직입시다 :)