계수 정렬 (Counting Sort)

목표

• Counting Sort에 대해 설명할 수 있다.
• Counting Sort 과정에 대해 설명할 수 있다.
• Counting Sort를 Python으로 구현할 수 있다.
• Counting Sort의 특징을 이해하여 시간 복잡도와 공간 복잡도를 계산할 수 있다.

요약

• 시간 복잡도가 O(n+k)로 매우 효율이 좋아보이는 정렬이다.
• 좋아보인다는 표현을 쓴 이유는 배열 내의 최댓값 k의 크기에 따라 오히려 효율이 나빠지기 때문이다.
  • n이 10일 경우, k가 1000이라면 O(10 + 1000)이기 때문에 O(n^3)이나 다를바 없다.
• k에 따라서 메모리도 많이 사용하게 된다.

과정 (오름차순)

1. 배열에 있는 숫자 중 가장 큰 값만큼의 배열을 만들어준다.
2. 주어진 배열을 순회하면서 카운팅 배열의 인덱스에 맞는 값의 수를 하나씩 증가시킨다.
3. 카운팅이 종료되면 누적합으로 바꿔준다.
4. 정렬할 배열을 뒤에서 앞으로 순회하면서 새로운 정렬에 하나씩 넣어줄 것이다.
5. 카운팅 배열에서 해당 숫자에 대한 값은 인덱스의 위치이다.
6. 새로운 정렬의 인덱스에다가 해당 숫자의 값을 넣고 카운팅 배열의 값을 하나 줄인다.
7. 4 ~ 6번 과정을 반복한다.

Python 코드

def countingSort(nums):
    max_num = max(nums)
    # 1. counting 배열을 생성하고 값을 증가시켜준다.
    counts = [0] * (max_num + 1)
    for num in nums:
        counts[num] += 1

    # 2. counting 배열을 누적합으로 바꿔준다.
    for c in range(1, len(counts)):
        counts[c] += counts[c - 1]

    # 3. counting 배열의 뒤에서 부터 앞으로 순회하면서 새로운 배열에 값을 쌓아간다.
    results = [0] * len(nums)
    for n in range(len(nums) - 1, -1, -1):
        results[counts[nums[n]] - 1] = nums[n]
        counts[nums[n]] -= 1

    return results

print(countingSort([5, 5, 3, 4, 19, 1, 0, 4, 1, 3, 0, 2, 4, 2, 3, 0]))

시간 복잡도

• Counting Sort의 경우 O(n + k)로 배열의 최댓값 k에 영향을 받는다.

공간 복잡도

k만큼의 배열을 만들어야 하기 때문에 O(k)이다.

특징

장점

1. 배열의 최댓값 k가 배열의 길이 n 보다 작다면 시간 복잡도가 O(n)으로 효율이 좋다.
2. 안정 정렬이다.

단점

1. 최댓값 k가 배열의 길이 n보다 많이 크다면 효율이 좋지 않다.
2. 정렬에 필요한 메모리가 많이 필요한 편이다.

Reference

• https://bowbowbow.tistory.com/8
• https://github.com/gyoogle/tech-interview-for-developer/blob/master/Algorithm/Sort_Counting.md
• https://www.zerocho.com/category/Algorithm/post/58006da88475ed00152d6c4b