페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#7094
스페셜 저지

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

문제

기수정렬이란?

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

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

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

  • LSD(Lowest Significant Digit) 방식: 가장 낮은 자리수부터 정렬하는 방식

  • MSD(Most Significant Digit) 방식: 가장 높은 자리수부터 정렬하는 방식

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

원리

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

  1. 배열의 가장 낮은 자리수부터 시작하여 각 자리수에 대해 정렬을 수행한다.

  2. 정렬이 완료되면 다음 자리수로 이동하여 동일한 정렬을 수행한다.

  3. 모든 자리수에 대해 정렬을 마치면 배열이 정렬된다.

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

  • 일의 자리수 기준 정렬:

    • [170, 90, 802, 2, 24, 45, 75, 66]

  • 십의 자리수 기준 정렬:

    • [802, 2, 24, 45, 66, 170, 75, 90]

  • 백의 자리수 기준 정렬:

    • [2, 24, 45, 66, 75, 90, 170, 802]

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

문제

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


입력

첫 줄에 정수 N과 정수 K가 주어진다. (5 \le N \le 55,\ 1 \le K \le 8)

두 번째 줄에 N개의 정수 A_1, A_2, ...\ ,A_N 이 주어진다. (0 \le A_i \le 2^{22})


출력

여러 줄에 걸쳐 정렬이 이루어질 때마다 수열 A를 출력한다.


예제 

8 3
170 45 75 90 802 24 2 666
24 170 90 802 2 666 75 45
2 75 24 90 666 802 170 45
2 24 45 75 90 666 170 802
2 24 45 75 90 170 666 802

괄호 안의 값들은 수열 A의 각 원소들을 2^3=8진법으로 바꾼 결과:

  • 170(252), 45(55), 75(113), 90(132), 802(1442), 24(30), 2(2), 666(1232)

1의 자리를 기준으로 정렬한 결과:

  • 24(30), 170(252), 90(132), 802(1442), 2(2), 666(1232), 75(113), 45(55)

8의 자리를 기준으로 정렬한 결과:

  • 2(2), 75(113), 24(30), 90(132), 666(1232), 802(1442), 170(252), 45(55)

64의 자리를 기준으로 정렬한 결과:

  • 2(2), 24(30), 45(55), 75(113), 90(132), 666(1232), 170(252), 802(1442)

512의 자리를 기준으로 정렬한 결과:

  • 2(2), 24(30), 45(55), 75(113), 90(132), 170(252), 666(1232), 802(1442)



출처

klee

로그인해야 코드를 작성할 수 있어요.