기수 정렬 (radix sort)

[radix sort]

 

radix : n 기수 (基數) : 십진법에서 10과 같이, 어떤 기수법의 체계의 기초로서 각 자리의 단위가 하나 위로 올라가기 위하여 필요한 배수

 

기수 정렬 (radix sort)

: 입력 데이터에 대해서 어떤 비교 연산도 실행하지 않고 데이터를 정렬할 수 있는 정렬 방법

 

여기서의 기수(radix)는 “숫자의 자리수” 정도로 이해할 수 있다.

<기수 란>

 

기수 정렬이 데이터를 상호간에 비교하지 않고 정렬하는 방법은 다음과 같다.

십진수에서 각 자리의 숫자는 0~9까지의 값만을 가질 수 있음으로 0~9까지의 각각의 버킷(bucket)을 만들고 데이터들을 각자 값에 따라서 버킷에 넣는다. 버킷을 0부터 순차 적으로 읽어서 값을 오름차순으로 정렬한다.

 

아래 그림은 (7, 6, 5, 8, 2, 9, 4)의 데이터를 기수 정렬을 사용하여 오름차순으로 정렬하는 과정이다.

<기수 정렬 과정>

 

(7, 6, 5, 8, 2, 9, 4)를 0~9 까지의 10개의 버킷을 만들어 해당하는 값을 버킷에 넣는다. 그 후에 0~9 순서대로 버킷안에 있는 데이터를 읽으며 오른쪽 배열의 왼쪽부터 차례대로 데이터를 채워 넣는다.

 

 

---

• 여러 자리로 이루어진 수를 정렬하는 과정

 

※ 낮은 자리수를 기준으로 먼저 정렬한 후에 높은 자리수로 정렬 해야한다.

 

왜냐하면

i ) 높은 -> 낮은 자리순으로 정렬하는 경우

<높은 자리에서 낮은 자리순으로 정렬하는 경우>

높은 자리부터 정렬하는 경우에는 <십의 자리로 분류>가 먼저 이루어진다.

언뜻 보기에 정렬이 제대로 이루어져 가는 듯 하지만 <일의 자리로 분류>가 이루어 지면서

오름차순으로의 정렬이 되지 못하고 엉망친창이 되었다.

 

 

 

ii ) 낮은 -> 높은 자리순으로 정렬하는 경우

<낮은 자리에서 높은 자리순으로 정렬하는 경우>

낮은 자리부터 정렬하는 경우에는 <일의 자리로 분류>가 먼저 이루어진다.

두 숫자 간의 크기를 비교할 때 일의 자리의 숫자가 아무리 큰들 십의 자리 숫자가 더 큰 수가 더 크다. 그렇기에 위 이미지에서 <일의 자리로 분류>가 먼저 이루어진 후에 <십에 자리로 분류>가 이루어진 배열은 오름차순으로 올바르게 정렬 되었다.

 

 

기수 정렬은 이렇듯 정렬의 단계의 수는 데이터의 자리수의 개수와 같다.

 

단계수 = 데이터의 자리수

 

이러한 기수 정렬은 모든 0~9의 버킷을 단계마다 만들어 추가적인 메모리를 필요로 하는 단점이 있지만, 이를 감안 하더라고 다른 정렬보다 빠르다는 장점으로 인하여 빈번하게 사용된다.