특수 정렬 알고리즘

  특수 정렬 알고리즘 

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

 

기수 정렬

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

 

기수 정렬 알고리즘

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

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

 

쉽게 배우는 알고리즘 특수 정렬 알고리즘 그림 3-12

 

계수 정렬

입력의 값이 모두 Ο(n)을 넘지 않는 경우 사용할 수 있는 정렬 방법으로 Θ(n) 이 소요되는 알고리즘이다.

 

계수 정렬 알고리즘

// A[]를 정렬한 결과가 B[]에 저장될 때
CountingSort(A[], B[], n)
{
    // 배열(혹은 딕셔너리) C[] 초기화
    for i ← 1 to k
    {
        C[i] ← 0;
    }
    // 값이 A[j]인 개수
    for j ← 1 to n
    {
        C[A[j]]++;
    }
    // 값이 A[j] 보다 작은 것의 개수
    for i ← 2 to k
    {
        C[i] ← C[i] + C[i - 1];
    }
    // B[]에 A[]의 자리를 확인하여 저장
    for j ← n downto 1
    {
        B[C[A[j]]] ← A[j];
        C[A[j]]--;
    }
}

 

NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)

GitHub - NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소

 

참고문헌

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