12-14-Radix-Sort

Radix Sort

---

Radix Sort

1의 자릿수부터 N의 자릿수까지 낮은 자릿수부터 정렬

• list[10] 배열을 선언하여 각 자릿수 인덱스에 리스트로 삽입

  list[0]: [100, 10, 20]
  list[1]: [1, 101, 91]
  ...
  

• 인덱스 0부터 각 요소들을 순서대로 배열에 정렬한 뒤, 10의 자리, 100의 자리 ... 똑같이 각 자릿수별로 정렬

시간복잡도

• 자릿수 최대 개수: D
• 리스트의 개수: K
• O(D(N+K))
• 리스트의 개수(K)는 N에 비해 무시 가능할만큼 작음: 최종적으로 O(DN)

---

정렬은 직접 구현하지말고 sort()를 이용해라!