기수정렬 Radix sort 기수정렬 정렬 방식 중 하나이다. 각 원소간 크기를 비교하지 않아서 빠른 시간복잡도를 가지고 있으며, 대신 별도의 메모리 공간이 필요하다. 시간복잡도는 O(dn)이다. 여기서 d는 모든 원소 중 가장 높은 자릿수를 의미한다. 예를들어 가장 높은 자릿수가 10만인 워스트케이스를 생각해보면 이 때 시간복잡도는 100000 x n이 되는것이다. 정렬방식 Step 1 1. 별도의 List 혹은 Queue를 만든다. 2. 배열의 각 원소를 List 또는 Queue에 넣는데, 이 때 각 원소의 1의자리 숫자에 해당하는 index를 찾아 배열 순서대로 넣는다. 3. 2번에서 별도의 테이블에 담은 원소들을 다시 초기 배열에 순서대로 넣는다. Step 2 Step 1과 동일하며, 봐야할 자릿..