[CLRS] [8-2] Radix sort(기수 정렬)

1. Radix Sort?

- Radix Sort는 여러 개의 자리수를 가진 정수나 문자열 데이터를 정렬할 때 효과적인 정렬알고리즘.

- 숫자를 비교하는 것이 아니라, 자리수를 기준으로 정렬을 수행하며,

- 각 자리수의 값을 이용해 한 번에 하나의 자릿수씩 정렬을 반복해 최종적으로 정렬을 완료함.

2. Radix Sort의 종류

2.1. LSD(Least Significant Digit)

- 가장 오른쪽 자리수(일의 자리)부터 왼쪽으로 이동하면서 정렬

- 일반적으로 정수를 정렬할 때 많이 사용됨

2.2. MSD(Most Significant Digit)

- 가장 왼쪽 자리수부터 시작하여 오른쪽으로 이동하면서 정렬

- 문자열이나 사전순으로 정렬할 때 주로 사용됨 

 

3. Radix Sort의 알고리즘(LSD 기준)

- Radix Sort는 자릿수마다 정렬을 수행하며 최종정렬을 완성한다.

- 10진수의 양수 배열을 정렬할 때 각 자릿수(일의자리, 십의자리, 백의자리)를 기준으로 정렬한다.

- 각 자리의 값을 기준으로 Counting Sort를 사용하여 정렬하면 된다. 

 

i) 최대 자릿수 계산:

- 배열 내 가장 큰 숫자의 자릿수를 게산하여, 몇 번의 자릿수 정렬이 필요한지 결정

 

ii) 자릿수별 정렬 반복:

- 일의 자리부터 시작해 각 자릿수별로 배열을 정렬

- 이를 위해 각 자릿수의 값을 기준으로 Countung Sort를 사용하여 정렬

 

iii) 최종 정렬 완료 

- 가장 큰 자릿수까지 정렬이 완료되면 전체 배열이 정렬됨

 

4. Radix Sort의 시간복잡도

- Radix Sort의 시간복잡도는 O(d*(n+k))이다.

d : 최대 자릿수

n : 배열의 크기

k : Counting Sort의 배열 크기 

 

5. Code 구현

def counting_sort_for_radix(arr,exp):
    n = len(arr)
    output = [0] * n 
    count = [0] * 10


    # 현재 자리수에 해당하는 count 배열 채우기
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    #누적 합 계산하여 정렬된 위치 계산
    for i in range(1,10):
        count[i] += count[i-1]

    i = n-1
    while i >= 0:
        index =  (arr[i] // exp) % 10
        output[count[index]-1] = arr[i]
        count[index] -= 1
        i -= 1

    for i,data in enumerate(output):
        arr[i] = data



def radix_sort(arr):
    max_val = max(arr)

    exp = 1
    while max_val//exp>0:
        counting_sort_for_radix(arr,exp)
        exp *= 10