기수 정렬

알고리즘

자리수가 $k$ 로 제한된 $n$ 개의 자연수로 이루어진 데이터가 주어져있다고 하자. 그러면 데이터는 다음의 알고리즘에 따라 정렬되며 그 시간 복잡도는 $O (n)$ 이다.

$i = 1 , \cdots , k$ 번째 자리수들끼리 비교해서 정렬한다.

설명

기수 정렬^{radix Sort}은 자리수의 제한이 있기 때문에 부동소수점이 있는 데이터에 적용할 수는 없으나, 정렬할 때 데이터간의 비교를 하지 않기 때문에 비교 정렬 알고리즘의 한계를 너머 선형 시간만에 데이터를 소팅할 수 있는 기발한 방법이다.

예시

$$ 190 \\ 812 \\ 9 \\ 77 \\ 21 \\ 413 $$ 가령 위와 같이 자리수가 $k=3$ 으로 제한된 $n=6$ 개의 데이터는 $3 \cdot 6 = 18$ 번만에 정렬이 끝난다. 우선 $i=1$ 번째 자리에 대해 정렬하고 나면 $$ 19 {\color{red}0} \\ 02 {\color{red}1} \\ 81 {\color{red}2} \\ 41 {\color{red}3} \\ 07 {\color{red}7} \\ 00 {\color{red}9} $$ $i=2$ 번째 자리에 대해 정렬하고 나면 $$ 0 {\color{red}0} 9 \\ 8 {\color{red}1} 2 \\ 4 {\color{red}1} 3 \\ 0 {\color{red}2} 1 \\ 0 {\color{red}7} 7 \\ 1 {\color{red}9} 0 $$ 마지막으로 $i=k$ 번째 자리에 대해 정렬하고 나면 $$ \color{red}{0} 0 9 \\ {\color{red}0} 21 \\ {\color{red}0} 77 \\ {\color{red}1} 90 \\ {\color{red}4} 13 \\ {\color{red}8} 12 $$ 여기서 주의해야할 점으로, $k$ 는 자리수라는 상수로 주어졌기 때문에 $kn = O(n)$ 지만 자리수가 데이터의 수보다 크면 당연히 $O(n^2)$ 가 된다. 이러한 경우에는 기수 정렬을 사용할 이유가 전혀 없으며, 비교 정렬 알고리즘을 사용하는 게 낫다.

증명

전략: 사실 위의 과정을 이해했다면 증명을 굳이 보아야할 이유는 없다.

$0$ 부터 $9$ 까지의 수를 정렬할 땐 각각의 수에 맞춰서 나눴다가 다시 합치면 된다. $0$ 이면 $0$ 끼리 모으고, $1$ 이면 $1$ 끼리 모으고, … , $9$ 면 $9$ 끼리 모은 배열을 만들고 순서대로 합치면 해당 자리수에 대해선 정렬이 끝난다. 이를 자리수 $k$ 만큼 반복하므로 총 수행 횟수는 $k n = O(n)$ 이 된다.

■

코드

다음은 기수 정렬을 줄리아로 구현한 것이다.

function row_sort(M, i)
    m = M[i,:]
    idx = vcat([findall(m .== "$digit") for digit in 0:9]...)
    return M[:, idx]
end
function radix_sort(arry)
    k = Int64(maximum(ceil.(log10.(arry))))
    M = stack(split.(lpad.(arry, k, '0'), ""))

    for i in k:(-1):1
        M = row_sort(M, i)
    end
    return parse.(Int64, reduce.(*, eachcol(M)))
end

arry = [190, 812, 9, 77, 21, 413]
radix_sort(arry)