기수 정렬1 기수 정렬 이번에 소개할 기수 정렬(Radix sort)도 지난번에 다룬 카운팅 정렬 처럼 두 요소의 대소관계 파악없이 진행하는 정렬법 입니다. 그리고 제가 기본적으로 소개할 기본적인 정렬방식의 마지막이기도 합니다. 1. 기수 정렬 기수 정렬은 요소의 대소 관계를 파악하지 않고 정렬하는 방식입니다. 기수 정렬의 시간 복잡도는 O(kn)으로 여기서 k는 요소의 최대 자릿수를 의미합니다. 즉, 정렬하려는 요소가 1의 자리라면 O(n)수준의 아주 빠른 시간 복잡도를 가질 것 이고, 1000, 10000의 자리 이런식으로 늘어날수록 시간 소모가 늘어납니다. 2. 기수 정렬의 동작 원리 기수 정렬은 각 요소를 분해해서 한자리 씩 비교합니다. 숫자라면 일의 자리는 일의 자리끼리, 문자열이라면 마지막 글자 끼리 비교합니다. 그.. 2021. 11. 7. 이전 1 다음 300x250
