[CS]계수 정렬(Counting Sort)
계수 정렬.
이름처럼 숫자를 세어 진행하는 정렬이다.
시간 복잡도는 O(n)으로 퀵 정렬 O(n log n), 합병 정렬(O(n log n)) 보다도 빠르다(!)
어떻게 이렇게 빠른 것일까??
계수 정렬이 이루어지는 방식은 다음과 같다.
1.정렬하는 배열의 최대 값을 크기로 가지는 배열을 하나 생성.
2.정렬하는 배열을 순회하면서 각 수들이 등장하는 빈도를 각 배열의 인덱스에 저장.
3.각 빈도를 누적한 합을 저장한 배열을 새로 생성한다.
4.다시 정렬해야 하는 배열을 역순으로 순회하면서 어떤 수가 나오면 누적합 배열의 해당 인덱스로 간다.
5.누적합 배열에 저장된 값을 인덱스로 하여 정렬된 값이 들어간 배열에 값을 저장한다.
6.누적합 배열에 저장된 값을 1씩 빼준다.
7.럼 숫자를 세어 진행하는 정렬이다.
시간 복잡도는 O(n)으로 퀵 정렬 O(n log n), 합병 정렬(O(n log n)) 보다도 빠르다(!)
어떻게 이렇게 빠른 것일까??
계수 정렬이 이루어지는 방식은 다음과 같다.
1.정렬하는 배열의 최대 값을 크기로 가지는 배열을 하나 생성.
2.정렬하는 배열을 순회하면서 각 수들이 등장하는 빈도를 각 배열의 인덱스에 저장.
3.각 빈도를 누적한 합을 저장한 배열을 새로 생성한다.
4.다시 정렬해야 하는 배열을 역순으로 순회하면서 어떤 수가 나오면 누적합 배열의 해당 인덱스로 간다.
5.누적합 배열에 저장된 값을 인덱스로 하여 정렬된 값이 들어간 배열에 값을 저장한다.
6.누적합 배열에 저장된 값을 1씩 빼준다.
7.위 과정을 원 배열의 역순회가 끝날때까지 반복한다.
import sys
def countingsort(entries):
preq = [0 for i in range(0,10001)]
aligned = 0*len(entries)
for a in entries:
preq[a] +=1
sums = 0
for x in range(0,len(preq)):
sums += preq[x]
preq[x] = sums
for n in reversed(entries):
aligned[preq[n]] = n
preq[n] -= 1
return aligned
input=sys.stdin.readline
num = int(input())
entries = []
for i in range(0,num):
entries.extend([int(input())])
entries = countingsort(entries)
for n in entries:
if n != 0:
print(str(n))
<작성 코드>
위 정렬은 빠르긴 하지만, 어떤 커다란 수가 나오는 경우 해당 값까지의 인덱스를 만들어야 하므로
상황에 따라 커다란 메모리 낭비를 초래할 수 있기 때문에, 때에 맞게 사용하는 것이 바람직하다.