[Algorithm] 기수 정렬 (Radix Sort)

 

 

 

 

기수 정렬 (Radix Sort)

기수 정렬은 비교하지 않는 정렬 알고리즘으로 낮은 자릿수부터 정렬을 수행.

 

• 숫자별로 버킷(bucket)이라는 queue를 생성
• 정렬하려는 숫자들의 각 자릿수에 해당하는 숫자를 각각의 버킷에 넣어 정렬
  • 이를 자릿수만큼 반복한다.

 

 

 

단점

• 버킷을 구성하기 위한 추가 메모리가 필요
• 정렬할 수 있는 데이터 타입이 한정적

 

예시

• 숫자 배열 [73, 21, 56, 13, 16, 35, 41, 69]를 기수 정렬을 이용해 오름차순으로 정렬하는 과정

  • 73

    21

    56

    13

    16

    35

    41

    69

1. 버킷

   • 0	1	2	3	4	5	6	7	8	9

2. 버킷

   • 	41 21		13 73		35	16 56			69
     0	1	2	3	4	5	6	7	8	9

3.  

   • 21

     41

     73

     13

     35

     56

     16

     69

4. 버킷

   • 	16 13	21	35	41	56	69	73
     0	1	2	3	4	5	6	7	8	9

5.  

   • 13

     16

     21

     35

     41

     56

     69

     73

 

시간 복잡도  :  O(dn)      * 데이터 개수 : n,  최대 자릿수 : d

 

 

 

def radix_sort(arr):
    RADIX = 10
    placement = 1
    max_digit = max(arr)
    
    while placement < max_digit:
        buckets = [list() for _ in range(RADIX)]
        for i in arr:
            tmp = int((i / placement) % RADIX)
            buckets[tmp].append(i)
        a = 0
        for b in range(RADIX):
            buck = buckets[b]
            for i in buck:
                arr[a] = i
                a += 1
        placement *= RADIX
    return arr