[Conflict - Merge] 기수정렬(Radix Sort)

[Conflict]

유클리드 최대 공약수 알고리즘이 최초의 알고리즘이라니 신기하네요. 알고리즘에 방정식을 사용하는 방법이라니, 소수를 찾는 것 역시 알고리즘으로 볼 수 있겠네..요..?있죠..? 글 읽다 보니까 '최근접 점의 쌍 찾기' 문제를 분할 정복 알고리즘을 사용하여 해결하는 과정이랑 시간 복잡도까지 이해가 됐어요. 진짜 자세하게 설명 다 되어있네요. 기수 정렬은 비교 정렬이 아니라 부분적으로 비교하는 정렬 방법이라고 하셨는데, 자릿수가 같은 것끼리, 자릿값이 같은 것끼리 정렬이 되는 건가요? 어떤 방식으로 동작하는 지 궁금합니다.

 

[Merge]

기수정렬(Radix Sort)은

낮은 자리수부터 비교하여 정렬해 가는 것을 기본으로 하는 정렬 알고리즘입니다.

 

기수 정렬 중에서도 2가지 방법이 있습니다

• 가장 작은 자리수 부터 비교하는 방법을 LSD(Least-Significant-Digit)
• 가장 큰 자리수부터 비교하는 방법을 MSD(Most-Significant-Digit)

기수정렬은 비교연산을 하지 않고, 정렬 속도가 빠르지만(시간복잡도 O(N)), 데이터 전체 크기에 기수 테이블 크기만한 메모리가 더 필요합니다(용량을 많이 잡아먹음).

 

기수정렬의 로직 예시

배열[222, 96, 123, 1, 23, 5, 2, 17, 28]

• 가장 큰 숫자 222, 자릿수 3

Phase1: 1의 자리수 기준 정렬

[1], [222, 2], [123, 23], [5], [96], [17], [28]

 

Phase2: 10의 자리수 기준 정렬

[1, 2, 5], [17], [222, 123, 23, 28], [96]

 

Phase3: 100의 자리수 기준 정렬

[1, 2, 5, 17, 23, 28, 96], [123], [222]