기수 정렬

This page was last edited on 1 June 2019, at 19:31.

기수 정렬(Radix sort)은 정렬 알고리즘의 하나이다. 기수 정렬은 레코드를 비교하지 않고 정렬을 수행하기 때문에, 비교를 기초한 방법들이 이론적인 하한선인 을 깰 수 없는 데 반해 시간복잡도를 가진다.[주 1] 기수 정렬의 단점은 추가적인 메모리를 필요로 한다는 것과 정렬할 수 있는 레코드의 타입이 한정된다는 것이다.

기수 정렬은 가장 낮은 자리수(Least Significant Digit;LSD)부터 혹은 가장 높은 자리수(MSD;Most Significant Digit)부터 할 수 있다. LSD 기수 정렬은 레코드의 안정성을 유지하는 것을 유념하여 낮은 자리수부터 차례로 버킷 정렬하면 된다. MSD 기수 정렬은 레코드를 높은 자리수부터 재귀적으로 정렬한다.

부연 설명

  1. d는 대부분 10 이하이다.
Retrieved from "https://femiwiki.com/index.php?title=기수_정렬&oldid=144577"