계수 정렬(Counting Sort) 의 개념

계수 정렬은 입력 원소의 값이 정수나 정수로 표현될 수 있는 값을 정렬할 때 사용할 수 있는 데이터 분포 기반 정렬 알고리즘입니다. 주어진 원소 중에서 자신보다 작거나 같은 값을 가지는 원소의 개수를 계산하여 정렬할 위치를 찾는 방식입니다.

계수 정렬의 Python 구현

Python 으로 계수 정렬을 아래와 같이 구현할 수 있습니다.

def counting_sort(arr: list) -> list:
    maximum = max(arr)
    count_arr = [0] * (maximum + 1)

    for i in arr:
        count_arr[i] += 1

    sorted_arr = []
    for i in range(len(count_arr)):
        sorted_arr.extend([i] * count_arr[i])

    return sorted_arr
  

위의 코드는 아래와 같이 동작합니다.

[7, 5, 9, 8, 4, 5, 7, 5]

먼저 알고리즘은 입력 배열에서 최솟값과 최댓값을 찾은 다음, 입력된 배열의 원소들이 얼마나 자주 등장하는지 기록할 배열 count_arr 을 초기화합니다.

[7, 5, 9, 8, 4, 5, 7, 5]

count_arr -> [0, 0, 0, 0, 0, 0]

그리고 입력 배열의 각 요소를 센 다음, count_arr 에 빈도수를 기록합니다. 4~5 의 범위에 대해서, 4는 한 번, 5는 세 번, … 9는 한 번 나타났네요.

[7, 5, 9, 8, 4, 5, 7, 5]

# 빈도수를 기록
# 4는 한번, 5는 세번, 6은 0번, 7은 2번 ...
 4, 5, 6, 7, 8, 9
[1, 3, 0, 2, 1, 1]

빈도수를 알고 있으므로, ("원소" * 빈도수) 대로 차례차례 배열을 재구성합니다. 예를 들면, 위의 예시에서 4는 한 번, 5는 세 번 나타났으므로 [4, 5, 5, 5 ... ] 가 될 것입니다.

[7, 5, 9, 8, 4, 5, 7, 5]

# 빈도수를 기록
 4, 5, 6, 7, 8, 9
[1, 3, 0, 2, 1, 1]

# -> 4, 555, 77, 8, 9
[4, 5, 5, 5, 7, 7, 8, 9]

계수 정렬의 성능 분석과 특징

• 계수 정렬은 입력 배열의 크기 n, k(최댓값 - 최솟값 + 1_) 에 대해서 O(n+k) 의 시간 복잡도를 가집니다.
  • 입력 배열의 최솟값과 최댓값을 찾는 과정에서, 알고리즘은 두 과정 모두 배열을 전체 탐색해야 합니다. 이 과정의 시간 복잡도는 O(n) 이 됩니다.
  • count_arr 을 초기화하는 과정에서, k(최댓값 - 최솟값 + 1) 의 값에 따라 시간 복잡도가 달라집니다. 이 과정은 k 의 크기에 따라 O(k) 의 시간 복잡도를 가집니다.
  • 이후 배열을 한번 루프하며, 각 원소의 빈도수를 계산합니다. 이 과정에서 O(n) 의 시간복잡도를 가집니다.
  • 빈도수가 계산된 후, 배열은 빈도수를 기록한 배열의 원소를 확인하고 그 값만큼 반복해 정렬된 배열을 생성하는데, 이는 O(n+k) 의 시간 복잡도를 가집니다.
• k 의 범위가 입력 배열의 크기 n 에 비례하는 경우에는 O(n) 의 시간 복잡도를 가집니다.
• 계수 정렬은 k 의 값이 입력 배열의 개수보다 작거나 비례해야만 선형 시간에 알고리즘이 동작합니다.
• 계수 정렬은 동일한 키값을 가지는 원소의 상대적인 위치가 유지되는 안정적 정렬 알고리즘입니다.
• 계수 정렬은 k 값에 해당하는 크기의 배열, count_arr 와 입력된 배열의 크기와 동일한 정렬된 배열(sorted_arr) 을 저장하기 위한 공간이 필요하기 때문에, 제자리 정렬 알고리즘이 아닙니다.