알고리즘...22

특수 정렬 알고리즘

두 원소를 비교하여 정렬하는 경우엔 수행 시간인 Ο(nlogn) 보다 빨라질 수 없다. 그러나 입력 값이 특수한 성질을 만족하는 경우 이러한 한계를 넘을 수 있는 알고리즘이 존재한다.

기수 정렬

입력이 모두 k 이하의 자리수를 가진 자연수인 경우 사용할 수 있는 정렬 방법으로 Θ(n) 이 소요되는 알고리즘이다.

 

기수 정렬 알고리즘

RadixSort(A[], n, k)
{
    for i ← 1 to k
    {
        i 번째 자리수에 대해 A[1...n]을 안정성을 유지하면서 정렬한다.
    }
}

※ 안정성을 유지한다는 것은 비교한 결과가 같으면 자리가 유지되어야 한다는 의미이다.

 

쉽게 배우는 알고리즘 정렬 기수 정렬 작동 예

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘