계수 정렬(Counting Sort)은 정렬 알고리즘 중 하나로, 입력 배열의 각 요소가 몇 번 나타나는지 세어서 정렬하는 방식입니다. 이 알고리즘은 입력 배열 내의 특정 범위 안에서만 동작하며, 정수나 정수에 해당하는 자료형에 주로 사용됩니다.

알고리즘 설명

계수 정렬은 다음 단계로 이루어집니다:

1. 입력 배열을 순회하며 각 요소의 발생 빈도를 센다.
2. 발생 빈도를 기반으로 정렬된 출력 배열을 생성한다.

예시를 통해 알고리즘을 살펴보겠습니다:

def counting_sort(arr, max_val):
    m = max_val + 1
    count = [0] * m
                
    for a in arr:
        count[a] += 1

    i = 0
    for a in range(m):
        for c in range(count[a]):
            arr[i] = a
            i += 1
    return arr

위의 예제에서 counting_sort() 함수는 입력 배열 arr과 최대 값 max_val을 받아서 계수 정렬을 수행합니다.

예제

arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr, 8)
print(sorted_arr)  # 출력: [1, 2, 2, 3, 3, 4, 8]

위의 예제는 입력 배열을 계수 정렬하여 정렬된 배열을 출력합니다.

계수 정렬은 입력 배열의 최대값에 비례하는 메모리를 필요로 하며, 따라서 입력 배열의 범위가 크면 메모리 사용량이 늘어날 수 있습니다.

결론

계수 정렬은 특정 범위 내에서 빠른 성능을 보이며, 입력 배열이 크지 않은 경우 유용하게 활용될 수 있는 정렬 알고리즘입니다.