정렬 알고리즘 #4. 빗질 정렬 (Comb Sort)

설명

빗질 정렬은 버블 정렬의 답답함을 해결하기 위해 고안된 비교적 간단한 정렬이다. 정렬을 거북이와 토끼에 비유를 했는데, 버블 정렬을 거북이라 비유하고, 해결하기 위한 방법으로 거북이를 토끼처럼 만드는 것으로 생각하였다

 

기본 설명

1. 기본 과정은 버블 정렬 (Bubble Sort) 와 동일하다

2. 특정한 감소량 (shrink factor) 를 통해 차이 (Gap)을 줄여가며 버블 정렬을 실행한다

3. shrink factor는 1.3이 가장 이상적이라는 소문이 있으나, 가장 빠른 수치로 결정하면 됨

4. Gap 이 결정되면 해당 대상과의 Gap 만큼 차이가 나는 노드의 크기를 비교하여 버블 정렬을 수행함

 

시간 복잡도

시간복잡도는 O(n^2)으로 버블 정렬을 개선했다고는 하나, shrink factor를 적절하게 잘 선택해야하는 이슈가 있으며, 역정렬을 행할때는 버블 정렬과 똑같은 시간복잡도를 가진다. 때문에 이게 버블 정렬보다 나은가는 shrink factor라는 변수와 전체 데이터셋이 잘 맞아야하기 때문에 효율적인지는 의문이다.

 

코드

void combSort(int *data, int n)
{
  float shrink = 1.3;
  int j, tmp, gap = n, swapped = 1;
 
  while(gap > 1 || swapped)
  {
    if ((gap/=shrink) < 1) gap = 1;
    for(j = swapped = 0; j < n-gap; j++)
    {
      if (data[j] <= data[j+gap]) continue;
     
      swapped = 1;
      tmp = data[j]; data[j] = data[j+gap]; data[j+gap] = tmp;
    }
  }
}