기수 정렬

기수정렬(radix sort) : 자리수의 값에 따라 정렬을 하는 다단계 정렬.

- 기수 : 숫자의 자리수

- 앞의 정렬방식은 레코드를 비교하여 정렬하는 방식, 비교 불가능한 레코드는 정렬할 수 없다.

- 추가 메모리가 필요하지만, 속도가 빠르기 때문에 많이 쓰인다.

- 단점으로는 정렬할 수 있는 레코드의 타입이 한정된다. 레코드들이 동일한 길이를 가지는 숫자, 문자열로 구성되어있어야 하기 때문.

- 별도의 버킷을 만들어 입력 데이터를 각 자리수의 값에 따라 넣고 왼쪽부터 순차적으로 버킷의 데이터를 읽어온다.

- 비교연산이 사용되지 않는다.

- 먼저 들어간 숫자는 먼저 나와야 하기 때문에, 버킷은 큐(queue)로 구성(숫자를 넣고 빼는 연산은 큐의 삽입삭제).

- 2진법 정렬시 2개의 버킷, 알파벳은 26개, 숫자는 10개.