계수 정렬 - Counting Sort

계수 정렬은 원소의 등장 횟수를 기반으로 정렬하는 효율적인 정렬 기법이다.
해당 알고리즘의 경우 진행 순서가 다음과 같이

1. 최댓값의 크기만큼 선언된 배열에서 index를 요소의 값으로 여기고 등장 횟수를 카운팅
2. 카운팅된 배열의 누적합을 구함
3. 기존 배열의 뒤에서부터 원소를 하나씩 빼며 -1한 값으로 카운팅된 배열의 index에 접근해 등장 횟수를 -1씩 줄임
4. 줄어든 등장 횟수가 곧 해당 원소의 정렬된 결과의 위치

이 과정에서 누적합을 구해야하는 이유가 무엇인지 이해가 잘 가지 않았는데, 그 이유를 알았다

기본적으로 정렬에는 두 가지 방법이 있는데,

1. Stable 정렬
2. In-place 정렬

누적합을 사용하게 되면 Stable 정렬을 수행할 수 있다. Stable 정렬이란, 정렬되기 이전의 각 요소들의 상대적인 위치가 정렬 이후에도 유지되는 것이다
예를 들어, 배열 [3, 1, 3, 5, 1, 6]가 있을 때, 정렬이 된 이후에도 index 0의 3이 index 2의 3보다 앞에 위치하는 것이다.

# Stable
arr = [3, 1, 3, 5, 1, 6]
dp = [0]*(max(arr)+1)
result = [0]*len(arr)

for elem in arr:
    dp[elem] += 1

for i in range(1, len(dp)):
    dp[i] += dp[i-1]

for elem in arr[::-1]:
	dp[elem] -= 1
    result[dp[elem]] = elem

print(result)

이러한 상대적 위치 보장이 중요하지 않은 경우에는 단순히 등장 횟수 배열에서 개수*원소 만큼 결과 배열에 추가해주면 되겠다. 이러한 경우 정렬의 결과는 동일하지만 기존 배열의 원소들의 상대적 위치가 보장되지 않을 수 있다. 이러한 정렬 방식이 In-Place 정렬이다.

# In-Place
arr = [3, 1, 3, 5, 1, 6]
dp = [0]*(max(arr)+1)

for elem in arr:
    dp[elem] += 1

result_arr = []
for idx, elem in enumerate(dp):
    result_arr.extend(elem * [idx])

print(result_arr)