- 기수 정렬
- 레코드 비교하지 않고 정렬 수행
- 비교에 의한 정렬의 하한인 𝑂(𝑛 log 𝑛) 보다 좋을 수 있다.
- 기수 정렬은 O(d*n) 의 시간 복잡도 (대부분 d<10 이하, d는 자릿수)
- 정렬할 수 있는 레코드의 자료형이 한정적이다 (실수, 한글, 한자 등 불가능)
- 레코드의 키들이 동일한 길이를 가지는 숫자나 단순 문자(알파벳 등)인 경우만 가능하다.
버켓
- 정렬을 위해 필요한 저장공간
- 숫자 10개 or 알파벳 26개
한자리수의 정렬
-> 우측의 정렬되지않은 수들을 각각의 버켓에 삽입한다. 이후 좌측처럼 버켓에서 위에서부터 순차적으로 수를 가져온다.
두자리수의 정렬
-> 우측의 정렬되지 않은 수들을 1의 자리에 맞춰 버켓에 삽입한다. 이를 상단의 버켓부터 순차적으로 가져온 것이 가운데의 수들이다. 이를 다시 10의 자리에 맞춰 버켓에 삽입 후 제일 좌측처럼 상단의 버켓부터 수를 가져오면 정렬된 결과가 나온다.
- 자릿수를 d라고 하면 각각의 자릿수마다 n번의 이동을 하므로 총 dn번의 이동이 발생한다.
