NeetCode 13번 알고리즘 : Counting Sort

니트코드 링크: https://neetcode.io/courses/dsa-for-beginners/13

Bucket Sort라고 나와있는데 설명되어 있는 것은 사실상 Counting Sort이고 Bucket Sort는 조금 다른 알고리즘이다.

Alogrithm

 

Code

def bucketSort(arr):
    # Assuming arr only contains 0, 1 or 2
    counts = [0, 0, 0]

    # Count the quantity of each val in arr
    for n in arr:
        counts[n] += 1
    
    # Fill each bucket in the original array
    i = 0
    for n in range(len(counts)):
        for j in range(counts[n]):
            arr[i] = n
            i += 1
    return arr

 

Complexity

Time Complexity : O(n)

정확히는 2n이다.

 

Memory Complexity: O(1)

array의 길이가 m, 수의 범위가 k라 할때

O(k)이므로 O(1)이다.

 

즉, time과 메모리 모두 Complexity 면에서 좋은데, 사용하지 않을 이유가 무엇인가?

 

Why Not Use?

정확히 리스트 안에 요소의 최소와 최대의 차이가 너무 크지 않을때만 효과 적이다.

주어진 배열의 크기가 3인데 그 안의 원소들이 1,100,100000이라고 해보자.

기존 배열의 크기는 3인데 새롭게 만들어지는 배열은 크기는 100000이 되어야 한다. 메모리적으로 굉장히 낭비가 심하다.

(반대로 배열의 길이가 긴데 그 안의 숫자의 범위가 작으면 counting sort는 메모리적으 매우 효과적이다. 백준 10989 참고)

 

또한, counting sort는 정수일때만 가능하다. decimal이나 word의 경우 sorting 불가능.