특수 정렬 알고리즘

앞에서의 알고리즘들은 원소 두개를 비교함으로서 정렬을 하는 비교정렬이고 이 비교정렬은 Θ(nlogn)을 넘지 못한다는 것이 알려져 있다. 이제 보일 알고리즘은 특수한 경우에서 이 한계를 극복할 수 있는 알고리즘이다.

 

1. 기수 정렬(Radix Sort)

기수 정렬은 입력이 모두 k 자릿수이하인 특수한 경우에 사용할 수 있다. 알고리즘은 아래와 같다.

그림을 보면 이해가 더 쉬운데

위와 같이 1번째 자리부터 그 한자리 수만 비교하여 정렬을 하는 것이다. 만일 같은 수일경우에는 순서를 유지하여 안정성을 유지한다. 이때 중요한 것이 만일 정렬을 할때 앞에서 나온 퀵정렬, 병합정렬등을 사용하게 되면 Θ(nlogn)이 나와서 다른 방법과 다를게 없게 된다. 따라서 미리 0~9의 자리가 들어갈 공간을 마련하여 그곳에 넣는 방법으로 Θ(n)의 시간복잡도를 가지게 한다. 직접 구현해본 코드는 아래와 같다. 파이썬을 이용하여서 딕셔너리를 이용해 공간을 마련하였다. 

def extract_num(num, i):
    divider = 10**(i)
    first = num%divider
    ans = first//(divider/10)
    
    return int(ans)


def radixSort(A, n, k):
    temp = A
    for i in range(1, k+1, 1):
        #make a room for each digits(using dictionary)
        dic = {}
        for j in range(10):
            dic[j] = []
        
        #extract the digits from each list elements and put the element is 
        #right dictionary
        for j in range(n):
            last_num = extract_num(temp[j], i)
            dic[last_num].append(temp[j])
        
        #rearrange the dic as one list
        temp = []
        for j in range(10):
            temp += dic[j]
        
    return temp

시간 복잡도는 Θ(kn+10k) = Θ(n)이된다.  

 

2. 계수 정렬(Counting Sort)

우선 알고리즘은 아래와 같다.

A배열에 있는 수가 k를 안넘을때 C는 k크기의 배열이며 A배열을 for문으로 하나씩 보면서 그 값에 대한 C의 배열로 가서 1을 추가해준다. 그다음 그 C의 수를 하나씩 지우며 새로운 B배열에 값을 추가해주는 방식이다. 이 방식은 원소들의 값이 n을 넘으면 안된다. 만약 n을 넘게 된다면 시간복잡도가 2Θ(k)+2Θ(n) 인데 k>n이면 시간복잡도가 Θ(k)가되고 이 k가 Θ(nlogn)을 넘게 되면 퀵정렬, 병합정렬들보다 효율이 떨어지게 된다. 

직접구현한 코드는 아래와 같다. 

def countingSort(A, n):
    #dic C to Count A elements
    C = {}
    #new array to store sorted list 
    B = []
    #initialize the C dic
    for i in range(1000):
        C[str(i)] = 0
        
    #counting the A list
    for i in range(len(A)):
        C[str(A[i])] += 1
        
    #store sorted list to B list
    for i in range(1000):
        while C[str(i)] > 0:
            B.append(i)
            C[str(i)] -= 1
            
    return B