[알고리즘] 데이터 분포 기반 알고리즘

데이터 분포기반 알고리즘은 이미 얻어진 데이터 분포정보를 활용하는 정렬 알고리즘입니다.

 

이러한 데이터 분포 기반 알고리즘에는 계수정렬, 기수정렬, 버킷정렬 등이 있으며 선형시간 O(n)이 가능합니다.

 

데이터 분포기반 알고리즘의 단점으로는 입력값의 범위를 미리 알아야 하며 특정조건에 맞게 제한적으로만 사용 가능하기 때문에 보편적이지 못한 정렬 알고리즘이 됩니다.

1. 계수정렬

주어진 데이터 중에서 자신보다 작거나 같은 값을 같는 데이터의 개수를 계산하여 정렬할 위치를 찾아 정렬하는 방식입니다. 계수정렬은 입력값이 어떤 작은 정수 범위내에 있다는 것을 알고있는 경우에만 적용가능합니다.

 

k보다 작거나 같은 값을 갖는 데이터의 개수를 알고 있을 때 이 데이터의 개수의 의미는 정렬 순서상 k의 마지막 위치를 의미합니다.

 

예컨대 입력데이터의 종류가 1,2,3이라고 했을 때 데이터의 개수가 2보다 작거나 같은 데이터의 개수가 4라는 것은 1의 개수와 2의 개수가 몇개인지는 모르지만 정렬을 했을 때 총 4개의 길이가 나오며 4번째에는 무조건 2가 위치하게 됩니다.

그렇다면 자신보다 작거나 같은 값을 갖는 데이터의 개수를 효율적으로 계산하는 방법은 입력값의 범위 a~b에 해당하는 크기의 배열 count[a,,b]를 할당하고, 주어진 값들을 한번 쭉 훑으면서 각 입력값의 출현횟수의 누적값 계산이 가능합니다.

1) 알고리즘

CountingSort(A[1,..n],n)
  {
  Min = Max = A[1];
  for(i=2;i<=n;i++){  //입력값의 범위 Min~Max 계
    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;j<=Max;j++)  // 각 입력값의 출현횟수의 누적값 계산
    Count[j] = Count[j] + Count[j-1];
  for(i=n;i>=1;i--){      // 입력배열 A[] -> 정렬배열B[]
    B[Count[A[i]]] = A[i];
    Count[A[i]]--;
  }
    return B;
  }

2) 성능과 특징

입력값의 범위가 데이터의 개수보다 작거나 비례할 때 유용하다는 특징이 있습니다.

 

입력값의 범위를 k라고 할 때 O(n+k) 시간이 걸립니다. 즉 k =O(n)이 되어야 선형시간 O(n)에 동작하게 됩니다.

그리고 계수정렬은 안정적인 정렬 알고리즘이 되지만, 제자리 정렬 알고리즘은 아닙니다.

 

 

2. 기수정렬

입력값을 자릿수별로 구분하여 부분적으로 비교하여 정렬하는 방식입니다.

주어진 데이터의 값을 자릿수별로 나누고, 각 자릿수에 대해 계수정렬과 같은 안정적인 정렬 알고리즘을 적용하여 정렬합니다.  이러한 기수 정렬은 진행방식에 따라 LSD 기수정렬과 MSD 기수정렬로 나뉩니다. LSD 기수정렬은 낮은 자리부터 높은 자리로 진행하는 방식이고 MSD 기수 정렬은 높은 자리부터 낮은 자리로 진행하는 정렬방식입니다.

1)  알고리즘

RadixSort(A[],n)
  {
    for(i=1;i<=d;i++){ //d자릿수 LSD 기수 정
      각 데이터의 i자리갓에 대해서 안정적인 정렬 알고리즘 적용;
    }
    return A
  }

2) 성능과 특징

계수정렬을 사용하기 때문에 O(dn)이 됩니다. 그런데 자릿수 d를 상수로 취급한다면 성능은 O(n)이 됩니다.

따라서 입력데이터의 자릿수가 상수일 때 유용합니다. 

그리고 기수정렬은 안정적인 정렬 알고리즘이지만 제자리정렬 알고리즘은 아닙니다.

 

3. 버킷정렬

주어진 데이터들의 값의 범위를 균등하게 나누어 여러개의 버킷을 만든 뒤, 각 데이터에 해당하는 버킷에 넣고 각 버킷을 삽입정렬과 같은 안정적인 정렬을 수행한 후, 버킷 순서대로 각 데이터를 나열하는 정렬방식입니다.

이러한 버킷정렬은 입력값의 범위 내에서 값이 확률적으로 균등하게 분포될 때 선형시간에 동작하게 됩니다.

 

1) 알고리즘

BucketSort(A[],n)
  {
    Min = Max = A[0];
    for(i=1;i<n;i++){ // 입력값의 범위 Min~Max 계산
      if(A[i] < Min) Min = A[i];
      if(A[i] > Max) Max = A[i];
    }
    Interval = |(Max - Min + 1) / n|; //버킷 구간의 크기 계산
    for(i=0;i<n;i++)               //각 데이터를 해당 버킷에 넣기
      A[i]를 버킷[(A[i] - Min) / Interval]에 삽입;
    for(i=0;i<n;i++)               // 버킷별로 정렬
      삽입정렬에 의해 버킷[i]를 정렬;
    버킷[0],버킷[1],... 순서대로 데이터를 배열B[]에 삽입;
    retrun B;
  
  }

 

2)성능과 특징

삽입정렬에 의해 버킷을 정렬할때 데이터가 균등하게 분포하고 있다면 성능은 O(n)이 되지만 특정 버킷에 데이터가 몰려있다면 성능은 O(n^2)이 됩니다.

따라서 이러한 버킷정렬은 입력데이터의 값이 확률적으로 균등하게 분포할 때 유용합니다. 또한 버킷의 개수가 입력데이터의 개수에 비례해야 유용합니다.

 

그리고 버킷정렬은 안정적인 정렬 알고리즘이지만 제자리 정렬 알고리즘은 아닙니다.