수 정렬하기 3

import sys


def main():
    input = sys.stdin.readline

    n = int(input())
    counts = [0] * 10001
    for _ in range(n):
        counts[int(input())] += 1

    for i, count in enumerate(counts):
        for _ in range(count):
            print(i)


main()

최악 시간 복잡도가 $O(n)$인 정렬 알고리즘

비교 기반 정렬 알고리즘의 최악 시간복잡도는 $O(n \log n)$보다 작을 수 없습니다. 그러나 원소를 서로 비교하지 않아도 된다면, 특히 원소가 정수고 범위가 한정되어 있다면 비교를 하지 않는 정렬 알고리즘으로 $O(n)$에 정렬할 수 있습니다.

실제로는 $O(n \log n)$과 $O(n)$의 차이가 크지 않고, 원소의 크기에 따른 제한이 있기 때문에, 특별한 경우가 아니라면 비교 기반 정렬로 문제를 풀면 됩니다.

계수 정렬 (Counting Sort)

def counting_sort(A: list[T]) -> list[T]:
    counts = [0] * (max(A) + 1)
    for a in A:
        counts[a] += 1

    result = []
    for i, count in enumerate(counts):
        result += [i] * count

    return result

계수 정렬(counting sort)은 개수를 세는 배열을 만든 후, 원소를 인덱스로 하여 개수를 셉니다. 그러고 나서, 개수만큼 인덱스를 결과 배열에 넣어주면 됩니다. 만약 위성 데이터도 있다면, 개수를 세는 배열 대신 리스트들의 리스트를 만들어 각 키에 해당하는 리스트에 위성 데이터를 삽입하면 됩니다.