Radix sort 공부를 하다가 Counting Sort를 다루게 되었는데 내 기억에는 배운 기억이 없어 정리를 하고 넘어가기로 했다.

영상으로 먼저 보고 공부를 시작했는데 CS Dojo 유튜브 를 보고 쉽게 이해할 수 있었다.

우선 Radix Sort는 Counting Sort를 이용해서 자릿수에 구애받지 않고 문자열이나 정수의 배열을 정렬할 수 있는 알고리즘이다. 비교하려는 문자열이나 정수의 base가 작거나 배열 중 최댓값의 자릿수가 적다면 Radix Sort가 Quick Sort나 Merge Sort보다 더 좋은 성능을 보일 수 있다.

Radix Sort의 시간 복잡도는 $O(d(n+k))$이다.

• $d$: 배열 내 최댓값의 자릿수
• $n$: 배열의 크기
• $k$: 배열 내 원소들의 base, 10진수일 경우 base = 10

Radix Sort는 배열 내 최댓값의 자릿수 만큼 Counting Sort를 진행해서 배열을 정렬하는데 그 전에 핵심 알고리즘은 Counting Sort를 짚고 넘어가자.

---

Counting Sort

같은 자릿수의 수들을 정렬할 때 사용하는 알고리즘이다. 예를 들어 다음과 같은 배열이 있다고 가정하자.

A = [1, 0, 3, 1, 1, 3]

Counting Sort는 각 원소끼리 비교를 하지 않고 배열 내 몇 번 등장(?)했는지 알아 내 정렬하는 알고리즘이다. 우선 각 원소들이 몇 번이나 등장했는지 세어보자. 그럼 다음과 같은 배열을 얻을 수 있다.

위와 같이 0은 1번,1은 3번, 3은 2번 등장한 것을 알 수 있다. 이 배열을 count 배열이라고 칭하자.

count = [1, 3, 0, 2]

이때 count 배열에서 이전 값을 계속 더해준다면 아래와 같은 배열을 얻을 수 있다.

count = [1, 4, 4, 6]

위와 같이 더해진 count가 의미하는 바는 무엇일까?
정렬된 A를 생각해보면, 0, 1, 1, 1, 3, 3에서 count에 해당하는 value값이 무엇을 나타내는지 규칙을 찾을 수 있다.

• 0 이란 원소는 0번째에 등장하고 0번째가 마지막 등장인데 count[0]의 값은 이때 1이다.
• 1 이란 원소는 1번째에 등장하고 3번째가 마지막 등장인데 count[1]의 값은 이때 4이다.

이전 값을 더해준 count가 의미하는 것은 즉, 마지막으로 등장한 index + 1을 의미한다.

마지막으로 등장한 index + 1, 구현하기도 생각하기에도 쉽지 않다.
그렇다면 오른쪽으로 shift해서 처음 등장한 index로 바꾸는 것은 어떨까?

이렇게 값을 오른쪽으로 한 칸씩 shift 해줬을 때 아래와 같은 의미를 얻을 수 있다.

이처럼 한칸 씩 이동한 배열의 값(value)은 각 원소(index)가 정렬된 배열에서 몇 번째 index에 처음 나타나는지 알 수 있다.

이제 count 배열을 이용해서 정렬하는 일만 남았다. 처음에 입력받은 배열과 count 배열을 사용해서 정렬을 진행한다.

A = [1, 0, 3, 1, 1, 3]
count = [0, 1, 4, 4]

배열 A의 첫 원소부터 순회를 시작한다.
A[0] = 1 에서 정렬되야하는 값은 1이다. 그리고 정렬되야하는 값 1이 정렬된 배열에서 처음 나타나는 index는 count[1] = 1이다. 그럼 아래와 같이 정렬될 수 있다.

sorted_A = [None, 1, None, None, None, None]

그리고 count[1] 을 +1 해주면 다음에 나타날 1의 index를 설정해줄 수 있다. 이를 코드로 작성하면 count[1] += 1이 되어 count배열은 아래와 같이 된다.

count = [0, 2, 4, 4]

이로써 정렬되야하는 1이 다음으로 나타날 Index는 2가 된다. 이런식으로 정렬하다보면 각 원소간에 비교를 거치지 않고 배열을 정렬할 수 있다. 소스 코드는 다음과 같다.

def counting_sort(arr, digit, base):
    result = [None for _ in range(len(arr))]
    count = [0] * base
    temp = [(x % base**(digit + 1)) // base**(digit) for x in arr]

    # count the element's appearance
    for t in temp:
        count[t] += 1
    # sum up the appearances
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    # set the first index of each elements to be shown
    for i in range(len(count) - 1, 0, -1):
        count[i] = count[i - 1]
    count[0] = 0
    # sort input
    for i in range(len(arr)):
        result[count[temp[i]]] = arr[i]
        count[temp[i]] += 1
    return result

$base^{digit}$ 이와 같은 관계이다.

• digit: 지수
• base: 밑
• result: 입력받은 배열의 크기만큼 선언해 정렬된 결과 값을 담는다
• count: base가 10이라면 총 0부터 9가 몇 번 등장했는지 더해주는 배열
• temp: 입력받은 digit에 따른 각 자릿수를 비교하기 위해 선언한 배열

위와 같은 Counting Sort를 이용해서 Radix Sort를 마무리 지을 수 있다. 소스 코드는 아래와 같다.

def radix_sort(arr, base):
    max_num = -1
    for a in arr:
        if max_num < a: max_num = a

    d = 0
    while max_num // base**(d) != 0:
        arr = counting_sort(arr, d, base)
        d += 1

    return arr

먼저 배열 내 최댓값을 알아내 자릿수를 파악해야한다. 이때 while문에서 자릿수만큼 Counting Sort로 비교를 해줘서 정렬된 배열 값을 얻어 낸다.

이처럼 비교를 거치지 않고 정렬할 수 있다는 점에서 각 자릿수가 작을 수록 효율적이고 빠른 Radix Sort에 대해서 알아보았다. 자릿수가 적다면 $O(n)$의 시간 복잡도를 가져 Quick Sort나 Merge Sort보다 더 효율적인 알고리즘이 될 수 있는 그런 알고리즘이다 🤩