정렬 알고리즘
-
카운팅 정렬(counting sort) - 정렬 알고리즘, 파이썬카테고리 없음 2019. 2. 19. 18:24
지금까지 배워온 정렬은 두 수의 대소를 '비교'하는 과정을 거쳐 정렬하는 comparison sort였습니다. 두 수를 반복적으로 비교해 정렬하는 comparison sort는 아무리 알고리즘을 잘 짜도 계산 복잡성이 O(nlogn)보다 큽니다. 예를 들어서 퀵 정렬(quick sort)의 계산 복잡성이 O(n^2)이고, 힙 정렬(heap sort)이 O(nlogn)이라는 점을 감안하면 이 같은 내용이 들어맞음을 확인할 수 있습니다. 하지만 counting sort는 non-comparison sort 기법으로 정렬에 드는 계산 복잡성을 O(n) 선까지 낮추려는 알고리즘입니다. - counting sort 예를 들어, 다음과 같은 input array에 대해 counting sort를 수행한다면, inp..