값끼리 비교하지 않고, 각 값이 몇 번 나오는지 세어서 들어갈 자리를 바로 계산합니다. 값의 범위가 작은 정수일 때 어떤 비교 정렬보다도 빠릅니다.

계수 정렬의 개수 세기, 누적 합, 자리 배치를 보여 주는 시뮬레이터

[자동 재생]을 누르거나 [다음 단계]로 한 단계씩 넘겨 보세요. 슬라이더를 끌면 원하는 단계로 바로 이동합니다. 아래 줄이 결과 배열 out이고, 오른쪽 아래에 count 배열이 있습니다.

시간O(n + k)

추가 공간O(n + k)

안정 정렬예

비교 횟수0번

조건작은 범위의 정수

누적 합이 자리를 알려 줍니다

count에 누적 합을 만들면 count[v]는 "v 이하인 값의 개수"가 되고, 이 수가 바로 v가 들어갈 구역의 끝 위치입니다. 원래 배열을 뒤에서부터 꺼내 구역의 끝부터 채우면, 같은 값끼리의 원래 순서가 유지됩니다. 이 안정성 덕분에 일의 자리, 십의 자리 순서로 계수 정렬을 반복하는 기수 정렬이 가능합니다.

k는 값의 범위입니다. 값이 0~10억처럼 넓으면 count 배열을 만들 수 없으므로 쓸 수 없습니다.

코테에서는: 개수가 많고 범위가 좁을 때

입력이 1,000만 개인데 값이 1만 이하라면 배열을 다 저장해서 정렬하는 대신, count만 채우고 count 순서대로 출력하는 편이 시간과 메모리 모두 유리합니다.

import sys
input = sys.stdin.readline
cnt = [0] * 10001
for _ in range(int(input())):
    cnt[int(input())] += 1
for v in range(10001):
    if cnt[v]:
        sys.stdout.write((str(v) + '\n') * cnt[v])