횽들 radix sort 많이 쓰이나요?

[익명(203.249)]

속도가 굉장히 빠른 것 같은데 소개좀 굽신굽신

[호랑정권(psyhou)]

기수정렬~! 아마 자리수정렬 방식으로 혁신적인 빠르기였지. 1의자리 정렬 10의 자리 정렬 요딴식 유사품 계수정렬

[흠좀물(vcdimension)]

radix sort는 counting sort의 발전형이니 우선 counting sort를 공부해봐. 핵심은 element끼리 비교하는 방식이 아니라(이건 lower bound가 n log n인게 증명돼있음) key값이 1인 원소들은 몇 개, 2인 원소들은 몇 개, .. 하는 식으로 가능한 모든 key값들에 대해 element 개수를 센 다음에 그냥 합쳐주는 방식.

[흠좀물(vcdimension)]

radix sort는 가장 높은 자리수부터 counting sort하는 방식으로, 예를 들어 key값이 3자리면 백의자리값을 가지고 sort -> 십의자리값끼리 sort -> 일의자리값끼리 sort 이렇게 하는 방식. 실세계의 key값은 가능한 값이 무한히 많겠지만 다루는 자료형은 결국 값의 범위가 32bit니 64bit니 하고 정해져 있으니까 예를 들면 8bit 단위로 끊어서 counting sort를 하겠다는 것이 radix sort야.

[흠좀물(vcdimension)]

근데 counting이나 radix나 complexity 자체는 O(n)이지만, 실제로 돌려보면 대부분 quick sort가 더 빠르대. quick sort는 각 구획별로 쪼개서 정렬하는 방식이기 때문에 캐쉬빨을 지대로 받을 수 있기 때문. 그리고 이것때문에 quick sort가 똑같이 O(n log n)인 merge sort나 heap sort보다 빠르다.

[익명(211.108)]

헐 radix 시간복잡도가 n이었음?