11. Array(배열) - Radix Sort

0. 시작하기 전에

- Radix Sort는 Counting Sort를 기반하기 때문에, Counting Sort를 알아야 한다. 

- 다음 포스팅에서 Counting Sort에 대해 익히기를 바란다. 

 

https://devraphy.tistory.com/438

10. Array(배열) - Counting Sort

 

---

1. Radix Sort(기수 정렬)

a) Radix Sort를 사용하는 이유 

- 다음과 같은 배열이 있다고 생각해보자.

- 이 배열을 Counting Sort를 이용하여 정렬한다면, 가장 먼저 count_array를 생성해야 한다.

- count_array를 생성할 때에는 max_num - nim_num + 1을 계산하여 배열의 길이를 만든다.

- 위의 배열의 경우 924 - 8 이므로, 917이라는 길이를 갖는 count_array가 생성된다. 

 

count_array = [0] * (924 - 8 + 1)

 

- 여기서 첫번째 문제점이 발생된다. 

- 7개의 요소로 이루어진 배열을 정렬하기 위해서 900여개의 count_array를 사용한다는 것이다. 

- 더불어 for문을 여러번 수행하는 counting sort의 경우, 900개 짜리의 배열을 계산하면 시간복잡도가 높아질 수 밖에 없다. 

- 즉, O(n + k)의 시간복잡도에서 k의 값이 엄청나게 커지는 것이다. 

 

- Radix Sort는 이러한 Counting Sort의 단점을 보완한 정렬방식이다. 

- Radix Sort는 Counting Sort와는 다르게 10개 짜리 배열을 사용해 요소들을 정렬할 수 있다.

- 왜 10개짜리 배열을 사용하는지, 어떻게 정렬하는지 알아보자. 

 

b) Radix Sort 정렬과정

- Radix Sort는 자릿수를 이용하여 정렬하는 방식이다. 

- 여기서 자릿수는 배열 요소 값의 1의 자릿수, 2의 자릿수, 3의 자릿수를 이용하여 정렬한다는 의미다.

- 가장 큰 배열 요소의 자릿수 만큼 정렬을 한다. 

 

- 다음 배열을 Radix Sort를 이용하여 오름차순으로 정렬해보자. 

▶ 자리 수 설정 

- 가장 큰 수는 924 다. 

- 3 자릿수 이므로 정렬에 사용될 자릿수는 3자리 까지다. 

 

▶  첫번째, 1의 자릿수를 이용한 정렬

- 이처럼 1의 자리를 기준으로 잡고 정렬을 시작한다.

- 여기서 가장 중요한 점 3가지를 알고가자. 

   * Radix Sort는 반드시 Stable한 정렬 방법을 사용한다.

   * Radix Sort는 Counting Sort를 사용하기 좋다. (자릿수를 이용한 정렬 방법으로, 정렬 기준이 0 ~ 9로 제한)

   * 정렬에 10개짜리 배열을 사용하는 이유 → 정렬 기준이 0 ~9로 제한되어 있기 떄문이다.

 

 

▶ 두번째, 2의 자릿수를 이용한 정렬

- 동일한 방식으로 2의 자릿수를 이용하여 정렬한다.

- 만약 2의 자리가 없는 요소의 경우, 0으로 처리한다. 

 

▶ 세번째, 3의 자릿수를 이용한 정렬 

- 이로써 정렬이 완료된 것을 확인할 수 있다.

- 이와 같은 정렬 방식을 Radix Sort라고 한다. 

---

2. 코드 구현

from typing import List
import math

def countingSortByDigit(nums:List[int],digit:int)->List[int]:  
  counts = [0]*10
  for num in nums:
    count_idx = num//pow(10,digit)%10
    counts[count_idx] += 1

  acc_counts = []
  acc_count = 0
  for count in counts:
    acc_count += count
    acc_counts.append(acc_count)
  end_locs = [ c-1 for c in acc_counts]

  sorted = [0] * len(nums)
  for num in reversed(nums):
    count_idx = num//pow(10,digit)%10
    end_loc = end_locs[count_idx]
    sorted[end_loc] = num
    end_locs[count_idx] -= 1

  return sorted


def radixSort(nums:List[int])->List[int]:
  largest_num = max(nums)
  digits = int(math.log10(largest_num))+1
  sorted = nums
  for digit in range(digits):
    sorted = countingSortByDigit(nums=sorted,digit=digit)
  return sorted

print(radixSort(nums=[391,582,50,924,8,192]))

---

3. 시간복잡도

- Radix Sort는 O( w * (n + k))의 시간복잡도를 가진다. 

- 여기서 W는 자릿수를 의미한다. 

- 여기서 k는 10으로 고정되어 있다.