기수정렬이란?

기수정렬은 정수를 자리수를 기준으로 정렬하는 알고리즘이다. 각 자리수를 기준으로 낮은 자리수부터 높은 자리수로 차례차례 정렬하여 최종적으로 정렬된 결과를 얻는다.

기수정렬은 계수정렬(Counting Sort)이나 버킷정렬(Bucket Sort)과 같은 다른 안정적인 정렬 알고리즘을 사용하여 각 자리수를 정렬한다.

기수정렬은 두 가지 방식으로 나뉜다:

해당 글에서는 일반적으로 사용되는 LSD 방식을 설명하겠다.

원리

LSD 방식의 기수정렬은 다음과 같은 단계로 이루어진다:

예를 들어, 배열 [170, 45, 75, 90, 802, 24, 2, 66]를 십진수 기준으로 기수정렬로 정렬하는 과정은 다음과 같다:

위에서 설명은 10진법 기반으로 했지만, \% 연산이 속도가 느리기에 실용적으로 사용하기 위해서는 2^K진법 기반으로 사용한다. 이는 자리수를 구하는 방법을 연산 속도가 빠른 비트 시프트(>>)를 이용한다.

문제

N개의 정수로 이루어진 수열 A와 정수 K가 주어졌을 때, 2^K진법으로 기수정렬한 수열 A를 LSD(Lowest Significant Digit) 방식으로 가장 낮은 자리수부터 정렬하는 과정을 정렬이 이루어질 때마다 출력하는 프로그램을 작성하시오.

기수정렬 (Radix Sort) - LSD timer 1s memory 1024MB

기수정렬 (Radix Sort) - LSD 1s 1024MB