Radix Sort(기수 정렬)

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다.

Radix Sort(기수 정렬)

낮은 자리 수 부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다.

자릿수가 고정되어 있으니, 안전성이 있고(이때 데이터들 간의 상대적 순서는 보존되어야 한다.)

기수 정렬은 비교 연산을 하지 않으며, 무엇보다도 전체 시간복잡도 역시 이어서, 정수와 같은 자료의 정렬 속도가 매우 빠르다.

하지만, 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다.

기수 정렬은 정렬 방법의 특수성 때문에, 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 사용 가능할 때에는 매우 좋은 알고리즘이다.

예시

329          720          720          329

457          355          329          355

657          436          456          436

839          457          839          457

436          657          355          657

720          329          457          720

355          839          657          839

(a)            (b)            (c)           (d)

(b) : 1의 자리수 정렬

(c) : 10의 자리수 정렬

(d) : 100의 자리수 정렬

의사코드

Radix-Sort(A, d) {    // A : n개 배열, d : 자리 형식
for i <- 1 to d
do use a stable sort to sort array A on digit;
}

소스 코드(Java)