Radix Sort

Radix Sort는 비교기반이 아닌 값의 분포를 이용한 정렬 알고리즘 입니다.

 

Radix이 한글로 기수라고 하는데, 나누기를 할때 몫에 해당하는 값이라고 합니다.

 

이때 10^n의 기수를 생각하면, 각 자리수를 이용해서 값을 정렬하는 알고리즘이라고 볼 수 있습니다.

1의 자리에 대한 Radix Sort 의 진행

첫번째 Element부터 1의자리를 비교하여, 해당 1의자리에 해당하는 List로 삽입을 진행합니다.

 

이렇게 모든 Element에 대해서 진행 후, 삽입된 List를 순서대로 풀어주면 한번의 Cycle이 끝납니다.

 

보시면 첫째자리의 값 기준으로는 모든 Element가 정렬된 것을 볼 수 있습니다!

 

이제 두번째 보시면, 왜 이런작업을 하는지 알 수 있습니다.

10의 자리에 대한 Radix Sort 의 진행

보시면, 10의자리 숫자를 기준으로 정렬할 때 1의자리 숫자의 정렬이 유지됩니다.(10의 자리수가 같은 숫자끼리)

 

이제 이 과정은 Max Num의 자리수만큼 반복하면,

 

이전의 Radix Sort로 미리 Max Num -1 자리수들 기준으로 정렬이 되어있기 때문에 모든 값이 정렬되게 됩니다!

 

이 알고리즘은 N개의 원소에 대해서, k(Max값의 자리수)만큼 반복하는 알고리즘 입니다.

 

따라서 시간복잡도가 O(kN) => O(N)의 선형의 시간복잡도를 보여주는 정렬알고리즘이 되겠습니다.

 

단, 해당 알고리즘은 숫자에만 사용이 가능하다는 단점이 존재합니다 ㅠ

 

Python으로 구현한 Radix Sort 알고리즘 소스코드입니다 :)

import random

class radix_sort:
    def __init__(self, DT_list):
        #각 자리수에 해당하는 Index를 가진 List를 준비합니다.
        self.number_list = [[] for i in range(10)]        
        self.ori_data = DT_list
        #입력된 Data의 가장 높은 자리수를 계산합니다.        
        self.Max_order = 0
        max_value = max(self.ori_data)        
        while True:
            if max_value<1:
                break
            max_value = max_value/10
            self.Max_order = self.Max_order +1 
    
    #Class 내에서 radix_sort 메쏘드를 정의합니다.
    def sort(self):        
        #큰 Cycle(모든 Element를 확인 후 해당 회차의 자리수를 확인 후 number_list에 넣는 것)
        #은 총 자리수(self.Max_order)만큼 진행합니다.
        for k in range(self.Max_order):
            #모든 Element에 대해서 0의자리~self.Max_order자리수를 산출해서
            #해당 자리수의 값에 해당하는 Index를 찾아 number List로 삽입합니다.
            for i in self.ori_data:                            
                #예를들어 100, 9999 Element가 있을 때 100의 천의자리는 0이 되는 것으로 취급합니다.
                if divmod(i,pow(10,k+1))[1]<1:
                    self.number_list[0] = self.number_list[0] + [i]
                #그 이외에는 Element의 값에서 현재 자리수의 값을 구합니다.
                #예를들어 98667가 있다면, 3번째 자리는 98667/1000의 나머지를 100으로 나눈 몫이 됩니다.
                else:
                    self.number_list[divmod(divmod(i,pow(10,k+1))[1],pow(10,k))[0]] = self.number_list[divmod(divmod(i,pow(10,k+1))[1],pow(10,k))[0]] + [i]
            #number_list에 Index별로 묶여있는 List를 풀어줍니다.
            self.ori_data = []
            for j in self.number_list:
                self.ori_data = self.ori_data + j            
            #number_list를 초기화 하고 다음 자리수에서 반복은 진행합니다.
            self.number_list = [[] for i in range(10)]   
        return self.ori_data
        
    
data = [random.randint(1, 1000) for i in range(50)]
=>[571, 365, 426, 387, 12, 445, 503, 939, 545, 334, 513, 636,\
   669, 833, 15, 898, 398, 226, 824, 545, 716, 323, 486, 54,\
   728, 247, 175, 329, 915, 634, 800, 821, 366, 531, 982, 446,\
   100, 548, 954, 985, 903, 536, 281, 803, 255, 748, 155, 458, 577, 875]
test = radix_sort(data)    
test.sort()
Out[58]: 
[12, 15, 54, 100, 155, 175, 226, 247, 255, 281, 323, 329, 334,\
 365, 366, 387, 398, 426, 445, 446, 458, 486, 503, 513, 531, 536,\
 545, 545, 548, 571, 577, 634, 636, 669, 716, 728, 748, 800, 803,\
 821, 824, 833, 875, 898, 903, 915, 939, 954, 982, 985]