기수정렬 (Radix Sort)

기수정렬 (Radix Sort)

이때까지의 정렬 방법들은 모두 레코드들을 비교하여 정렬했습니다. 따라서 비교가 불가능한 레코드는 정렬할 수 없었습니다.

기수정렬은 레코드를 비교하지 않고도 정렬하는 방법입니다.

- 입력 데이터에 대해 어떠한 비교 연산도 실행하지 않고 데이터를 정렬할 수 있는 기법

기수란 숫자의 자리수입니다.

- 예를 들면 숫자 42는 4와 2의 두개의 자리수를 가지고 이것이 기수가 됩니다.

기수정렬은 이러한 자리수의 값에 따라 정렬을 하기 때문에 기수정렬이라는 이름을 얻었습니다.

{8, 2, 3, 7, 5}

를 정렬하기 위해 10진수라는 점을 착안하여 10개의 버킷을 만들고 입력 데이터를 각 자리수의 값에 따라 상자에 넣습니다.

그리고 각 왼쪽 상자부터 순차적으로 버킷 안에 들어있는 숫자를 읽습니다.

그러면 정렬된 숫자를 얻을 수 있습니다.

버킷의 갯수

- 이진법 2개

- 십진법 10개

- 알파벳 26개 등

기수정렬의 특징

기수정렬은 O(kn)으로 가장 빠릅니다. 하지만 기수 정렬이 추가적인 메모리를 필요로 한다는 것인데 이를 감안하더라도 기수 정렬이 다른 정렬보다 빠르기 때문에 데이터를 정렬하는 상당히 인기있는 정렬이라고 할 수 있습니다.

문제점으로 정렬에 사용되는 키값이 숫자로 표현되어야만 적용이 가능합니다.

- 한글, 한자 등으로 이루어진 키 값을 기수정렬 하려면 매우 많은 버킷이 필요하므로 기수 정렬의 적용이 불가능합니다.

- 반면, 다른 정렬 방법들은 모든 종류의 형태에 적용이 가능합니다.

기수정렬의 구현

출처 : http://wonjayk.tistory.com/224