기수 정렬

선형 시간 복잡도(O(n))의 정렬 방식에 대해 공부하다 책(두잇 자.알.파.)에 나와있지 않은 기수 정렬이란 것을 발견했다.

그래서 한번 공부 해보고 구현을 해보았다.

기수 정렬이란

기수를 기준으로 정렬을 하는 것이다. 작은 자릿수부다 기수 정렬을 반복하여, 최대 값의 자릿수 까지 비교하면, 완전히 정렬을 끝마치게 된다.

도수 정렬은 배열 안의 모든 숫자에 대한 인덱스를 가지고 있는 배열을 생성해야하기 때문에 메모리를 많이 사용하는데, 기수 정렬은 도수 정렬에 비해 메모리는 적게먹고, 시간 복잡도는 선형으로 나오기 떄문에 꽤나 활용도가 높은 알고리즘이다.

N = int(input())
arr = [int(input()) for _ in range(N)]


def radix(arr, exp):
    count = [0]*10
    result = [0]*N

    for n in arr:
        count[n//exp % 10] += 1

    for i in range(1, N):
        count[i] += count[i-1]

    for i in range(N-1, -1, -1):
        result[count[arr[i]//exp % 10]-1] = arr[i]
        count[arr[i]//exp % 10] -= 1

    arr = result[:]
    return arr


m_val = max(arr)

exp = 1
while m_val // exp != 0:
    arr = radix(arr, exp)
    exp *= 10

print(arr)

구현 시에 에로 사항

기수로 카운팅 하는 배열에는 개수만 담겨있고 숫자가 담겨있지 않은 문제였다.

나 같으면 멍청하게 이차원 배열을 활용했겠지만, 역시 고수는 발상이 다르다.

기본적으로 방법은 이렇다. 각 숫자별로 들어가는 횟수를 누적해서 더함으로써 누적합산이 하나의 인덱스로써 활용될 수 있도록 하는 절차를 추가한다. 그 인덱스를 활용해 다시 숫자를 기수 정렬한 배열을 하나 더 만들고 원래 배열을 업데이트 한다.

이해하는 데만 해도 오래 걸렸다. 남들보다 지능이 떨어지는 만큼 배로 더 열심히 해야할 것 같다.