기수 정렬(Radix sort)

목차

1. 기수 정렬이란?
2. 사용 예시
3. 장점과 단점

1. 기수 정렬이란?

기수 별로 비교 없이 수행되는 정렬 알고리즘입니다.
기수로는 낱말, 정수 들 사전순으로 정렬할 수 잇는것으로만 가능합니다.
보통 숫자에 한정한 단순 오름차순, 내림차순의 경우 작은 기수(일의 자리 수)부터 정렬을 시작합니다.

2. 사용 예시

다음의 숫자를 오름차순으로 정렬해 보겠습니다.

우선 10개의 큐를 준비합니다. 각 큐에는 각 기수별로 해당하게 되는 원소를 잠시 저장할 것입니다.

앞서 설명했듯 가장 작은 기수(일의 자리 수)부터 확인합니다.
제일 처음 원소'70'의 경우 일의 자리 수가 0입니다. 그렇기 때문에 0큐에 70을 저장합니다.
이런식으로 각 큐에 원소들을 차례대로 저장합니다.

해당 원소들을 다시 밖으로 꺼내는 과정입니다. 단 꺼내는 순서는 큐(0)부터 큐(9)까지 순서대로 출력하게 됩니다.

가장 낮은 기수에서의 과정이 끝났으니 그 다음으로 낮은 기수(십의 자리 수)에서 동일한 과정을 거칩니다.

3.장점과 단정

3-1. 장점

정렬 속도가 매우 빠릅니다.
최대 기수 크기를 d, 원소의 갯수를 n이라고 할때 시간복잡도가 O(dn)으로 매우 빠른 편에 속합니다.

3-2. 단점

위 예시는 숫자만으로 보여드렸기에 큐 10개만으로도 가능했습니다.
하지만 앞서 말씀드렸다싶이 사전적으로 정렬할 수만 있다면문자열이나 기타 기호 등으로도 관계없이 사용되기 때문에 큐를 준비하기위한 공간 복잡도가 큰 편에 속합니다.