[자료구조] 기수 정렬(Radix Sort)

목차

정렬 종류
비교 기반 정렬(Comparison Based Sorts) 
- Selection Sort, Bubble Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort
비비교 기반 정렬(Non-comparison Based Sorts)
- Counting Sort, Radix Sort, Bucket Sort

 

기수 정렬(Radix Sort)

개념

• Radix Sort는 기존 Counting Sort(계수 정렬) 방식에서의 단점을 보완하기 위해 나온 방법입니다. Counting Sort의 경우 K(최댓값과 최솟값의 차이)가 커지게 되면 메모리를 많이 차지하게 되어 작업 속도가 느려질 수 있어 Counting Sort의 장점이 사라지게 됩니다. 또한 Counting Sort의 경우 제한되지 않은 문자열에 대해서는 쉽게 처리를 할 수 없습니다. (abcd라고 한다면 알파벳 크기만큼의 진수법을 생각해서 숫자로 변경시켜야 합니다. 하지만 이는 문자열이 너무나도 길어지게 된다면 K가 너무 커지게 될 것입니다.)
• Radix Sort에는 몇 가지 방법이 있지만, 그중에서 LSD(Least Significant Digit) Radix Sort에 살펴보겠습니다.
• LSD Radix Sort는 각 정수의 가장 오른쪽(문자열의 경우 가장 오른쪽 문자)부터 시작하여 해당 숫자에 대해서만 계산 정렬을 수행하는 것입니다. 이렇게 정렬을 할 경우 앞에 숫자가 같더라도 뒤에 문자에 따라 정렬이 미리 된 상태이기 때문에 그 순서를 유지할 수 있습니다.
  • 예를 들어 , 14 12 11 이 있다고 할 때 먼저 일의 자리먼저 Counting Sort를 통해 정렬을 진행하면 11 12 14가 됩니다. 그다음 십의 자리로 정렬을 하더라도 11 12 14가 그대로 유지가 됩니다. (일의 자리를 미리 정렬해 두었기 때문에 십의 자리가 같은 경우에 십의자리 순서대로 정렬을 하더라도 그 순서가 유지됩니다.)
• 시간복잡도는 O(w(n+k))가 될 것입니다. w는 자릿수, k는 한 자리에서 가능한 범위입니다. (즉, 만약 4자릿수를 정렬할 때 counting sort를 이용한다면 O(n+10000)이 되지만 radix sort를 사용하면 O(4(n+10))으로 해결이 가능해집니다. )
• 공간복잡도의 경우는 O(n+k)입니다. 기존의 자리수를 정렬하고 나면 그 배열을 그대로 사용하면 되기 때문에 w를 곱하지 않아도 됩니다. 따라서 기존 counting sort에 비해 확연한 공간절약이 가능합니다. (즉, 만약 4 자릿수를 정렬할 때 counting sort의 경우 O(n+10000)이지만, radix sort는 O(n+10)입니다.)

코드

• Radix Sort
  • shift를 빼주는 이유는 음수를 처리하기 위함입니다.

  • def counting_sort(arr, radix, K):
        counts = [0 for _ in range(K)]
    
        for item in arr:
            digit = (item // (K**radix)) % K
            counts[digit] += 1
    
        starting_index = 0
        for i, count in enumerate(counts):
            counts[i] = starting_index
            starting_index += count
    
        sorted_arr = [0 for _ in range(len(arr))]
        for item in arr:
            digit = (item // (K**radix)) % K
            sorted_arr[counts[digit]] = item
            counts[digit] += 1
    
        for i in range(len(arr)):
            arr[i] = sorted_arr[i]
    
    
    def radix_sort(arr, K=10):
        shift = min(arr)
        arr[:] = [num - shift for num in arr]
        max_item = max(arr)
    
        radix = 0
        check_value = 1
        while check_value <= max_item:
            counting_sort(arr, radix, K)
            radix += 1
            check_value *= K
    
        arr[:] = [num + shift for num in arr]
    
    
    arr = [907, 256, 336, 736, 443, 831]
    radix_sort(arr)
    print(arr)

출처

• https://leetcode.com/explore/learn/card/sorting/695/non-comparison-based-sorts/4438/