[Algorithm][Python] 계수 정렬(Counting Sort) 알고리즘 + 코드

이번에는 제가 가장 좋아하는 정렬 알고리즘인 계수 정렬(Counting Sort)에 대해 작성해보겠습니다. 문제 풀이를 하면서 상당히 많이 계수 정렬을 이용한 풀이를 포스팅했습니다. 계수 정렬을 굳이 사용했던 이유는 너무 많지만 계수 정렬을 알게 된 이유는 백준 문제 때문이었네요. counting sort 정도로 빠른 정렬 알고리즘을 사용하지 않으면 풀 수 없는 문제가 있었던 것으로 기억합니다(비고에도 counting sort를 알아보라는 말이 적혀있었구요). 그게 계기가 되어서 계수 정렬을 공부했고 처음엔 이게 무슨 말인가 싶었는데 익숙해지니까 속도도 빠르고 직관적이라 자주 쓰게 되었네요.

 

계수 정렬

그렇다면 계수 정렬(Counting Sort)은 무엇일까요? 위키피디아에 따르면 양의 정수를 키로 하여 개체 모음을 정렬하는 알고리즘 이라고 나오는데요. 양의 정수를 키로 한다는게 약간 감이 잘 안오실 수도 있습니다. 계수 정렬의 로직을 글로 풀어서 설명을 하면, 주어진 모든 숫자가 나오는 횟수를 세어서 순서대로 정렬하는 알고리즘입니다. 거기서 횟수를 셀 때 해당 정수를 키로서 사용을 하게 되죠. 어째 말을 하면 할수록 헷갈리는 기분입니다. 한 번 그림으로 알아볼까요?

저는 계수 정렬 보다는 counting sort라고 부르는 것을 선호하는데 알고리즘의 로직을 직관적으로 알 수 있는 이름이라는 생각이 들어서입니다. 이름 그대로 counting을 하고 그걸 토대로 정렬을 하니까요. 아마 나중에 코드까지 보시면 확실히 이해가 되실겁니다.

 

사실 위의 그림만 가지고는 바로 이해하기는 어려울 것 같아서 글을 좀 더 써보자면, 주어진 데이터에서 어떤 숫자가 몇 번 나왔는지를 체크하고 해당 숫자들이 나온 갯수만큼 새로 써주는 방식을 갖고 있습니다. 예를 들어서 7 7 4 2 2 4 6 9 1 3 6 의 숫자들이 입력으로 주어진다면 맨 앞에서부터 숫자가 나온 갯수를 세어가는 거죠. 7 : 2개, 4 : 2개, 2 : 2개, 6 : 2개, 9 : 1개, 1 : 1개, 3 : 1개가 있네요. 이렇게 나온 숫자를 카운트하고 작은 수부터 나온 갯수만큼 쓰면 오름차순, 큰 수부터 하면 내림차순의 정렬이 되게됩니다.

 

https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

Counting Sort

위 링크는 제가 counting sort를 이해하는데 도움을 많이 받았던 사이트라서 올려봤습니다. 애니메이션이 있어서 반복해서 보다보면 이해가 되실거에요.

 

이번에는 코드를 보도록 하겠습니다. 알고리즘은 로직을 보고 직접 코드를 짜보면 바로 이해가 되는 경우가 제법 있기 때문에 코드도 함께 짜보면 좋을 것 같네요.

def counting_sort(data):
    max_num = max(data)
    cnt = [0 for i in range(max_num + 1)]
    sorted_data = []
    for i in data:
        cnt[i] += 1
    for i in range(max_num + 1):
        for j in cnt[i]:
            sorted_data.append(i)
    return sorted_data

코드는 이렇게 작성해볼 수 있을 것 같습니다(물론 제가 짠 것보다 훨씬 효율적인 코드가 있을 수 있습니다). 제 코드를 기준으로 설명을 드려보면, 먼저 주어진 데이터에서 가장 큰 값(max_num)을 찾고 max_num만큼의 길이를 갖는 카운팅 리스트를 만들어줍니다. 그리고 반복문을 통해 배열의 모든 원소를 돌면서 데이터의 값을 인덱스로 활용해 카운팅 리스트의 원소를 증가시킵니다. 예를 들어서 데이터의 원소가 7이었다면 cnt[7]의 값이 1 증가하게 됩니다. 그렇게 모든 데이터의 원소를 다 카운팅했다면 sorted_data에 카운팅 리스트의 '인덱스'를 추가합니다(카운팅 리스트의 인덱스가 원래 데이터의 숫자이고 값이 갯수임을 잊지마세요). 이렇게 하면 오름차순으로 정렬된 리스트를 얻을 수 있게됩니다.

 

위에서 사용했던 7 7 4 2 2 4 6 9 1 3 6 이것을 이용해보겠습니다. 먼저 max_num을 찾겠죠. max_num은 9입니다. 그럼 길이가 최소한 9를 인덱스로서 사용할 수 있는 사이즈가 되어야 하므로 cnt의 길이는 max_num + 1인 10이 됩니다(1을 더해주지 않으면 인덱스를 8까지밖에 사용할 수 없습니다). 그리고 나중에 값을 추가할 sorted_data라는 빈 리스트를 생성해줍시다. 이제는 반복문을 통해서 카운트를 증가시킬겁니다. 처음 원소가 7이니까 cnt[7]의 값이 1 증가합니다. 다음도 7이니까 cnt[7] += 1, 그 다음은 4니까 cnt[4] += 1, cnt[2] += 1 ... cnt[6] += 1 까지 돌고 반복문을 탈출합니다. 이번엔 반복문을 이용해 cnt를 돌면서 해당 값(갯수)만큼 인덱스(원래 숫자)를 sorted_data에 저장할겁니다(i는 0부터 커지니까 오름차순으로 정렬이 됩니다). 1은 1개니까 1개만 추가되고 2는 2개니까 2개 추가, 3은 1개 추가, 4는 2개 추가... 마지막으로 9는 1개 추가해서 sorted_data는 [1, 2, 2, 3, 4, 4, 6, 6, 7, 7, 9] 가 됩니다.

 

약간 숫자 카드 놀이처럼 생각해도 이해가 편할 것 같습니다. 가지고 있는 숫자 카드들을 바닥에 무작위로 늘어놓고, 같은 것끼리 모아놨다가 나중에 낼 때 작은 숫자부터 내는거죠.

 

계수 정렬의 특징

counting sort가 어떤 로직을 갖고 있는지 위에서 알아봤습니다. 그렇다면 counting sort의 특징에는 무엇이 있을까요? 일단 보통 사용하는 정렬 알고리즘과는 확실히 다른 느낌을 가지고 있다는 것은 알겠는데 뭐가 다른 점이고 어떤 장단점이 있을까요?

 

계수 정렬의 시간 복잡도

counting sort는 빅오표기법(Big-O Notation)기준으로 보통 O(N)의 시간복잡도(실제로는 N보다는 오래걸립니다. 그래서 점근 표기법임에도 O(N + K) 라고 적기도 하죠, K : 카운팅 리스트의 사이즈)를 갖습니다. 많이들 사용하는 quick sort나 merge sort가 O(NlogN)의 시간복잡도를 가지니까 정말 빠른거죠. 하지만 어디까지나 보통의 상황일 경우만 그렇습니다. 코드로 확인을 했지만 counting sort의 경우 특정 상황에서 상당히 비효율적일수밖에 없는 구조를 갖고 있죠. 예를 들어서 입력이 [4, 7, 1, 2, 10000000000000000000000000000] 로 들어온다고 해봅시다. quick sort나 merge sort는 딱히 큰 문제없이 정렬을 할 수 있겠지만 counting sort는 max_num 만큼의 사이즈를 갖는 리스트를 만들어야 하기 때문에 메모리를 엄청나게 잡아먹게 됩니다(당연히 저렇게나 사이즈가 큰 리스트면 생성도 오래 걸리고 나중에 호출할 때도 시간이 많이 걸립니다). 따라서 max_num이 크지 않을수록 이득이 많은 정렬 알고리즘이라고 볼 수 있겠습니다.

 

제한적인 사용처

counting sort는 상당히 제한적인 상황에서만 사용이 가능합니다. 일단 주어진 입력을 카운팅 리스트의 인덱스로 사용해야하기 때문에 입력이 무조건 정수여야 합니다. 실수형 데이터에는 적용할 수 없죠. 그리고 보통은 0을 포함한 양의 정수에만 사용을 합니다. 음의 정수 데이터에는 약간 코드를 변형하면 사용가능합니다. 하지만 보통은 양의 정수에만 사용을 하죠. 또 위에서도 나왔지만 특정 값이 다른 데이터들의 평균값과 차이가 많이 나면 구조적인 문제로 인해 상당히 비효율적인 알고리즘이 되어버립니다.

 

장점

뭐니뭐니해도 압도적인 속도가 장점입니다. 위에서 나온 이런저런 조건만 만족시켜주면 가장 빠른 속도를 보여줍니다. 빠르다는 quick sort도 O(NlogN)이니 말 다했죠. 특히 적은 입력의 갯수에 비해 범위가 적을수록 효과가 좋습니다(그래서 시험 점수로 정렬할 때 쓰면 좋겠다는 글도 있더라구요). counting sort는 대부분의 정렬 알고리즘과 다르게 비교 정렬이 아닙니다. 따라서 비교를 하는 연산 자체가 필요없으니 그런 부분에서 시간을 아낄 수 있죠.

 

단점

장점과 마찬가지로 위에서 나왔던 조건에 부합하지 않는 경우 아예 사용하지 못하거나, 상당히 비효율적이라는게 단점이 되겠습니다. 뭐 어떻게 다 좋을 수 있겠나 싶기도 하지만요.

 

오늘은 이렇게 계수 정렬(Counting Sort)에 대해서 알아봤습니다. 위에서도 말했지만 저는 counting sort 알고리즘을 정말 좋아하는데요. 해당 이유에는 알고리즘 문제에서 보통 입력이 정수로 주어지고 구현이 간단한 점, 그리고 시간이 빠르다는 점이 있습니다. 어지간한 정렬 문제는 입력을 보고 정수다 싶으면 바로 counting sort로 짜버리면 쉽고 빠르게 풀 수 있습니다. 뭔가 설명을 잘하고 싶었는데 글만 잔뜩있는 포스팅이 되어버렸네요. 짬짬이 애니메이션을 만들어서 한 번 추가해보겠습니다.