알고리즘...23

계수 정렬

입력의 값이 모두 Ο(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]]--;
    }
}

 

참고문헌

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