10강 제5강 정렬 알고리즘 (계수, 기수)(정렬 알고리즘의 비교)

5.9 계수 정렬

 

5.9.1 개념과 원리

> 비교 기반이 아닌 데이터의 분포를 이용한 정렬 

   * 계수 counting 정렬, 기수 radix 정렬 → 선형 시간 O(n)

 

> 주어진 원소 중에서 자신보다 작거나 같은 값을 갖는 원소의 개수를 계산하여 counting 정렬할 

   위치를 찾아 정렬하는 방식

  * 입력값이 어떤 작은 정수 범위 내에 있다는 것을 알고 있는 경우에만 적용 

    ** 입력값의 범위 a~b에 해당하는 크기의 배열 COUNT[a..b]를 할당하고, 각 입력값을 한 번 훑으면서 

        각 입력값의 출현 횟수의 누적값을 계산하여 이용

 

 

5.9.2 알고리즘

CountingSort(A[],n)

입력 : A [1.. n] : 입력 배열

       n:입력 크기

출력 : B [1.. n] : 정렬된 배열

 {

   MIN = MAX = A [1];       // 입력값의 최솟값 최댓값을 계산하여 키의 범위를 계산

   for( i = 2; i <=n; i++)

     {

        if ( A [i] < MIN ) MIN = A [i];

        if ( A [i] > MAX ) MAX = A [i];

     }

   for( j = MIN; j <= MAX; j++ ) COUNT [j] = 0;    // 출현 횟수의 누적 값을 초기화

   for( i = 1; i <= n; i++ ) COUNT [A [i]]++;            // 각 입력값의 출현 횟수 계산

   for( j = MIN + 1; j <= MAX; j++ )                   // 출현 횟수의 누적 값 계산

      COUNT [j] = COUNT[j] + COUNT [j-1];

   for( i = n; i  > 0; i-- )                                   // 입력 배열의 오른쪽 끝부터 정렬을 진행

     {

          B [COUNT [ A [i] ] ] = A [ i ];                    // 정렬 A []  -> B []

          COUNT [ A [ i ] ]--;                               // 해당 입력값의 마지막 위치를 조정

      }

   returnB;

} 

 

계수 정렬의 적용 예

  입력 값의 출현 횟수 누적

 

 

 

 

 

누적 값 계산

 

누적값 

4 = 1 (4 >= 값 개수 )

5 = 4 (5 >= 값 개수 )

6 = 4 (6 >= 값 개수 )

7 = 6           :

8 = 7           :

9 = 8 (9 >= 값 개수 )

 

5라는 데이터의 정렬된 마지막 위치는 

4번째,

 

 

예)

A : 7번째 데이터의 값 7의 정렬된 마지막 값은 6 

 

B : 6 번째 자리에 7을 입력

 

후 , 7의 누적 값 6은 1 감소시킨 5가 됨

 

 

 

 

예 2)

A : 6 번째 데이터의 값 5의 정렬된 마지막 값은 3

 

B : 3 번째 자리에 5를 입력

 

후 , 5의 누적 값 3은 1 감소시킨 2가 됨

 

 

 

 

반복 

 

 

 

 

 

 

 

 

 

 

 

 

 

5.9.3 성능 분석 

 

CountingSort(A [], n) 

{ 

   MIN = MAX = A [1];

   for( i = 2; i <= n; i++ )

     {

          if( A [i] < MIN ) MIN = A [i];  k = MAX - MIN +1

          if( A[i] > MAX ) MAX = A[i];

      }

   for( j = MIN; j <= MAX; j++) COUNT [j] = 0;

   for( i = 1; i <= n; i++ ) COUNT [A [i]]++;

   for( j = MIN+1; j <= MAX; j++ )

      COUNT [j] = COUNT [j] + COUNT [j-1];

   for(i=n;i >0;i--)

   {

      B [COUNT [A [i] ] ] = A [ i ];

      COUNT [A [i]]--;

    }

   returnB;

} 

O( n + k ) 입력값의 범위 k 가 입력 크기 n에 비례하면 O(n)

 

 

5. 9. 4 특징

> 입력값의 범위가 입력 원소의 개수보다 작거나 비례할 때 유용

   - 입력값의 범위를 k라고 할 때 O(n+k) 시간 

    -- 보통 k=O(n) 일 때 사용하므로 결국 선형 시간 O(n)을 가짐 

> 안정적인 정렬 알고리즘

> 제자리 정렬 알고리즘이 아님 

> 보편적이지 못한 방법

  - 입력값의 범위를 알아야 함

  - 추가적인 배열이 필요 → COUNT [], B []

 

 

5.10 기수( radix sort ) 정렬

5.10.1 개념과 원리

> 입력값을 자릿수 별로 부분적으로 비교하는 정렬 방식

  - 주어진 원소의 키값을 자릿수별로 나누고, 각 자릿수별로 계수 정렬과 같은 

    안정적인 정렬 알고리즘을 반복적으로 적용하여 정렬 

  - LSD LeastSignificantDigit 기수 정렬 → 낮은 자리부터 높은 자리로 진행

  - MSDMostSignificantDigit기수 정렬 → 높은 자리부터 낮은 자리로 진행

 

5.10.2 알고리즘

RadixSort(A [], n)

{

   for( i = 1; i <= d; i++)

     {     //d 자릿수, LSD기수 정렬

          각 원소의 i자리의 값에 대해서 안정적인 정렬 알고리즘을 적용;

      }

   returnA;

}

 

 

입력 값들의 일의 자리를 보고 정렬

 

 

그다음 십의 자리 값을 보고 정렬

 

 

마지막으로 백의 자리 값을 보고 정렬 후 결과 도출

 

 

5.10.3 성능 분석 

 

RadixSort( A [] , n)

{

   for( i = 1; i <= d; i++ )

     {   // d 자릿수, LSD기수 정렬

     각 원소의 i자리의 값에 대해서 안정적인 정렬 알고리즘을 적용;

     //  >>>>>>>>>> 계수 정렬을 사용하면 O(n)

     }

   returnA;

}     >>>>>>>>>>  시간 복잡도 O(dn) d가 입력 크기 n보다 매우 작으면 

O(n)

 

 

5.10.4 특징

> 입력 원소의 값의 자릿수가 상수일 때 유용

  - d자릿수 n개의 숫자들에 대해 계수 정렬을 적용하면 O(dn)

   -- > 여기서 d를 상수로 간주하면 O(n) 

> 안정적 정렬 알고리즘

> 제자리 정렬 알고리즘이 아님

  - 계수 정렬 → 전체 데이터 개수와 진법 크기만큼의 추가적인 공간이 필요

 

 

 

 

2020/05/05 - [방송통신대학/알고리즘] - 10강 제5강 정렬 알고리즘 (합병, 퀵, 힙, 비교 기반 하한)

불러오는 중입니다...

 

11강 제 6장 탐색 알고리즘

불러오는 중입니다...