12. 기수 정렬 (A.K.A Radix sort)
알고리즘 공부
2019. 9. 29.
기수 정렬 출처: https://youtu.be/LyRWppObda4 기수 정렬 알고리즘 중 LSD를 시각화한 것. 시간 복잡도는 (k는 데이터의 자릿수를 의미한다.) 데이터끼리 직접적인 비교를 하여 정렬하는 알고리즘의 경우 시간복잡도는보다 작아질 수 없다. 기수 정렬은 자릿수가 있는 데이터(정수, 문자열 등)에서만 수행이 가능하며, 데이터끼리의 직접적인 비교 없이 정렬을 수행한다. 비교를 이용한 정렬이 아니기 때문에 k가 상수일 경우 시간복잡도가으로, 퀵정렬보다 빠른 시간복잡도가 나오는 것이 가능하다. 다만 이 알고리즘은 자릿수가 적은 4바이트 정수 등에서나 제대로 된 성능을 발휘할 수 있으며, 자릿수가 무제한에 가까운 문자열 정렬 등에 사용할 경우 오히려 퀵정렬보다 느릴 수 있고, 부동 소수점의 경우..
