Radix Sort에 대해 설명해보세요

---

Radix Sort의 작동 방식

• 기수 정렬은 낮은 자리수부터 비교하면서 정렬하는 알고리즘이다. 비교 연산을 하지 않기 때문에 빠른 속도로 정렬이 가능하지만 자릿수가 존재하지 않는 데이터에 대해 정렬은 불가능하다. 가장 작은 자리수부터 비교하는 방법을 LSD(Least-Significant-Digit), 가장 큰 자리수부터 비교하는 방법을 MSD(Most-Significant-Digit)이라고 한다. 일반적으로 LSD를 많이 사용한다.

1. 배열 안에서 가장 큰 숫자의 자릿수(d)를 구한다.
2. 중간 결과를 저장할 큐(Queue) 자료구조를 사용한 버킷(Bucket)을 준비한다.
3. 일의 자리 숫자부터 가장 큰 자리 숫자까지 자리별 숫자를 비교하여 정렬한다.

초기 상태의 배열

1의 자리 비교 과정

10의 자리 비교 과정

100의 자리 비교 과정

---

Radix Sort의 특징

• 시간 복잡도
  : 각 데이터를 버킷에 저장하는 과정을 최대 자릿수(d)만큼 하기 때문에 O(dN)의 시간 복잡도를 가진다.

• 공간 복잡도
  : 데이터 종류에 따라 추가적인 메모리 공간이 필요하다.

• 장점

  • 문자열과 정수 정렬이 가능하다.
  • 같은 두 수가 있어도 순서가 바뀌지 않는다.

• 단점

  • 추가 메모리 공간이 필요하다.
  • 부동 소수점과 같이 자릿수가 없는 데이터는 사용할 수 없다.

---

결론

Radix Sort는 각 자리수 별로 데이터를 비교하여 정렬하는 방식입니다. LSD의 경우 가장 작은 자리수부터 최대 자리수까지 비교하여 정렬합니다. 이때 최대 자리수를 d라고 했을 때 시간 복잡도는 O(dN)을 가집니다. 빠른 속도로 정렬이 가능하나 중간 결과를 저장할 버킷이 사용되기 때문에 추가 메모리 공간이 필요하다는 단점이 있습니다.