[알고리즘] 기수 정렬(Radix Sort)

기수 정렬

삽입, 병합, 퀵 정렬등의 비교기반 정렬과 다르게

비교 연산을 하지 않는다

추가적인 메모리도 필요하다

즉, 공간을 희생하여 시간 효율을 높이는 방법

 

기수(Radix) 란 숫자의 자릿수이다

기수 정렬은 이러한 자릿수의 값에 따라서 정렬한다

다단계 정렬이며, 단계의 수는 데이터의 전체 자릿수와 일치

 

 

한 자릿수의 정렬

 

1. 항목들을 저장할 버킷들을 준비

2. 입력 항목들을 순서대로 킷값에 따라 해당 버킷에 넣음

3. 위쪽 버킷부터 순차적으로 버킷 안에 들어 있는 숫자를 출력

 

여러 자리 숫자의 정렬

 

먼저 낮은 자릿수로 정렬한 다음 차츰 높은 자릿수로 정렬

 

 

 

여러 자리의 숫자를 정렬하는 방법을 구체적으로 생각해보자

 

숫자를 십진법으로 나타내면 버킷은 10개를 사용

같은 숫자를 2진법으로 표현한다면 버킷 2개 필요

키가 영어 알파벳 문자(a~z)라면 버킷 26개 필요

 

버킷에 여러 개의 숫자가 들어 갔을 때 먼저 들어간 숫자가 먼저 나와야한다

그래야 이미 정렬한 자릿수에 의한 숫자들의 상대적인 순서가 계속 유지된다

따라서 버킷은 큐(Queue)로 구현