Count sort - 계수 정렬

정렬 대상의 원소의 범위를 알 수 있을 때 적용할 수 있는 정렬 방법이다.

• 계수를 이용하여 원소의 중복 횟수를 구하고 이를 순서대로 출력한다.

import sys
from random import randrange

N = int(sys.stdin.readline())
lst = [randrange(1, N, 1) for _ in range(N)]

print("정렬 전 : {}".format(lst))

count = [0] * (N + 1)
for i in lst:
    count[i] += 1
ans = [str(i) * j for i, j in zip(range(N + 1), count)]

print("정렬 후 : {}".format("".join(ans)))