빗질 정렬(Comb Sort)

💡 빗질 정렬(Comb Sort)이란?

Bubble Sort의 단점인 거북이 데이터를 개선하고자 gap을 1보다 크게 설정.
gap만큼 차이나는 두 숫자를 비교하여 두 수의 정렬 순서가 맞지 않는 경우 교환(swap)하는 정렬.

❓ Bubble Sort의 거북이 데이터(turtle data)란?
Bubble Sort 실행 시, 오른쪽에서 왼쪽으로 매우 느리게 제 위치로 이동하는 작은 데이터들

👉 gap

• 비교하는 두 데이터의 거리. Bubble Sort에서의 gap은 1임
• 각 Pass가 진행됨에 따라 k만큼 gap을 줄여감
  gap의 크기: [n/k, n/k^2, n/k^3, ... , 1]
  ☺︎ 권장되는 k 값: 1.3
• gap의 크기에 따라 Comb Sort의 효율성이 달라짐

👉 gap>1인 단계에서 거북이 데이터를 제 위치의 인근에 옮겨 놓았기 때문에 gap=1에서 실행되는 pass 횟수는 Bubble Sort로만 진행할 때보다 줄어듬

✔️ 빗질 정렬 구현

void swap(int* a, int* b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}


void combSort(int array[], int n){
    float shrink = 1.3;

    int sorted = 0;
    int gap = n;

    while(!sorted){
        gap = floor(gap/shrink);
        if(gap <= 1){
            gap = 1;
            sorted = 1;
        }

        for(int i=0; i+gap<n; i++){
            if(array[i] > array[i+gap]){
                swap(array[i], array[i+gap]);
                sorted = 0;     // gap이 1일 때 정렬이 끝나지 않은 상황. 다시 한번 sort하기 위한 설정
            }
        }
    }
}

✔️ 특징

✔︎ Not Stable
✔︎ In-place