개발 공부 - [정렬] sorting in linear time : Radix Sort

 Radix Sort

: n개의 d자리 정수들

: 가장 낮은 자리수부터 정렬

* 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다.

* 전체를 비교하기 때문에 시간 복잡도 상으로는 O(w+n) 이라고 함.

강의에서는

Radix-sort(A(n개의 데이터가 저장된 배열), d(여기에 저장된 각각의 자리가 d자리 정수))

for i <- 1 to d

    do use a stable sort to sort array A on digit i

                 ㄴ counting sort를 쓰면 n+k 이기 때문에... ㄱ

그냥 d번 반복문을 돌면서 sort 하는 구조 = O(d(n+k))

https://youtu.be/eCnKp9bzErg?t=1143 시점에 보면 그동안 나왔던 것에 대한 시간복잡도가 나와 있음.

참고 : https://lktprogrammer.tistory.com/48