이번 챕터에서 공부 할 Data Structure는 Radix Sort, 기수 정렬이다.

기수 정렬은 다른 정렬 방법과 달리 숫자들 끼리 비교하지 않는 비 비교 알고리즘이다.

그리고 굉장히 빠른 정렬 방법 중 하나이며 정렬을 하더라도 순서가 바뀌지 않는 안정 정렬이다.

기수 정렬의 시간 복잡도는 O(kn) 인데, k 는 가장 큰 수의 자릿수이다.

예를 들어, 342389 가 가장 큰 수 라고 했을 때 k = 6 이고 O(6n)이 되는 셈이다.

다만 기수 정렬은 제자리 정렬이 아니기 때문에 추가적으로 사용하는 메모리가 발생하여

O(n)의 공간 복잡도를 가지게 된다.

이 정렬을 사용하기 위해서는 두 가지의 조건이 필요하다.

1. 숫자 형식의 배열만 가능하다. (ex. ["Apple", "Grape", "Monkey"] 와 같은 리스트는 정렬 불가능. )
2. 부동소숫점이 없는 정수 타입만 가능하다. (ex. [32.546, 45.233, 10.247] 과 같은 리스트는 정렬 불가능.)

위의 조건들을 만족하지 않으면 기수 정렬은 사용할 수 없다. 그리고 기수 정렬에는 두가지 방법이 있는데, 가장 작은 수 부터 비교하는 LSD(Least Signficant Digit) 와 가장 큰 수 부터 비교하는 MSD(Most Significant Digit)가 있다. 우리가 공부할 기수 정렬은 LSD 이다.

let var = [40, 39, 18, 819, 14, 1385]

위의 배열을 이용하여 기수 정렬이 무엇인지 단계별로 알아보자.

1. 가장 낮은 자리 수인 1의 자리수만 비교해서 정렬을 한다.

   → [[40], [14], [1385], [18], [39, 819]]

2. 그 다음으로 낮은 자리 수인 10의 자리수를 비교하여 정렬한다.

   → [[14, 18, 819], [39], [40], [1385]]