기수 정렬(Radix Sort)

기수 정렬(radix sort)는 정렬할 원소의 키 값을 나타내는 숫자의 자리 수(10의 자리수, 1의 자리수 등)를 기초로 정렬하는 기법이다. 

이는 80칼럼 punched card를 정렬시키거나 도서관 목록 카드 정렬과 같은 생활 응용에 많이 활용된다.

예를 들어 [437,123,234,578,351,625,543] 을 정렬하면 다음과 같다.

1단계(1의 자리 수 기준 정렬) : [351,123,543,234,625,437,578]

2단계(10의 자리 수 기준 정렬) : [123,625,234,437,543,351,578]

3단계(100의 자리 수 기준 정렬) : [123,234,351,437,543,578,625]

 

이에 따른 기수 정렬 ADL은 다음과 같다.

radixSort(a[],n)
	for (k <- 1; k <= m; k <- k+1) do { // m = digit 수, k = 1은 가장 작은 자리 수
    	for (i <- 0; i < n; i <- i+1) do {
        kd <- digit(a[i],k); // k번째 숫자를 kd에 반환
        enqueue(Q[kd],a[i]); // Q[kd]에 a[i]를 삽입
    }
    p <- 0;
    for (i <- 0; i <= 9; i <- i+1) do {
    	while (Q[i] != 공집합) do { // Q[i]의 모든 원소를 a[]로 이동
        	p <- p+1;
            a[p] <- dequeue(Q[i]);
        }
    }
 }
end radixSort()

 

간단하기 떄문에 예시는 생략한다

python code는 다음과 같다.

def enqueue(queue,data): queue.append(data)
def dequeue(queue):
    if len(queue) == 0:
        print('Empty')
        return -1  
    else:
        data = queue.pop(0)
        return data
def digit(d,k):
    temp = 1
    for _ in range(1,k):
        temp *= 10
    d = int(d/temp)
    d %= 10
    return d

def radixSort(a,n,m,queue):
    for k in range(1,m+1):
        for i in range(1,n+1):
            kd = digit(a[i],k)
            enqueue(queue[kd],a[i])
        p=0
        for i in range(10):
            while len(queue[i]) != 0:
                p += 1
                a[p] = dequeue(queue[i])


import random,time
if __name__ == '__main__':
    M = 5
    N = 100000
    a = []
    a.append(-1)
    for i in range(N):
        a.append(random.randint(1,99999))
    Q = []
    for i in range(10):
        Q.append([])
    start_time = time.time()
    radixSort(a,N,M,Q)
    end_time = time.time()-start_time
    print('RadixSort Runtime(N=%d) : %0.3f'%(N,end_time) )

시간 복잡도는 O(N)이다.