[알고리즘 개념] Comb Sort

Comb Sort란?

• Bubble Sort에서 거북이(turtle) 데이터를 줄이고자 고안해낸 알고리즘입니다.
  • 토끼(rabbit) 데이터는 bubble sort에서 문제가 되지 않습니다.
  • Not stable하면서 In-place한 Algorithm입니다.
• Bubble Sort에서는 인접한 두 데이터의 크기를 비교합니다.
  • 비교하는 두 데이터의 거리를 gap이라 합니다.
  • Bubble sort에서는 바로 인접한 데이터를 비교하기때문에 gap이 1입니다.
• Comb sort
  • gap의 크기를 1보다 크게합니다.
  • bubble sort의 각 pass가 진행됨에 따라 gap의 크기를 줄여갑니다.
    • "shrink factor"를 k 만큼 줄여갑니다
    • gap의 크기 : $$ [\frac{n}{k},\frac{n}{k^2}, \frac{n}{k^3}....,1 ] $$
    • gap의 크기에 따라 comb sort의 효율성이 달라집니다. 이때 권장되는 k의 값은 1.3입니다.

Comb Sort 코드

 

#include <stdio.h>
#include <iostream>
#include <cmath>
#define MAX_SIZE 1000
using namespace std;
void combSort(int a[], int n);
int main()
{
    int numTestCases;
    scanf("%d", &numTestCases);
    for (int i = 0; i < numTestCases; ++i)
        {
        int num;
        int a[MAX_SIZE];
        scanf("%d", &num);
        for (int j = 0; j < num; j++)
                scanf("%d", &a[j]);
            combSort(a, num);
            printf("\n");
        }
        return 0; 
}
void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp; 
}
/* comb sort 함수 */
void combSort(int a[], int n)
{
    float shrink = 1.3;
    
    bool sorted = false;
    int countCmpOps = 0; // 비교 연산자 실행 횟수 
    int countSwaps = 0; // swap 함수 실행 횟수
    int gap = n;
    // comb sort 알고리즘 구현
    while(sorted == false){
        gap = floor(gap/shrink);
 
        if (gap <= 1){
            gap = 1;
            sorted = true;
        }

        int i = 0;
        while(i + gap < n){
            countCmpOps ++;
            if(a[i]>a[i+gap]){
                swap(&a[i],&a[i+gap]);
                sorted = false;
                countSwaps ++;
                i ++;
            }
            else{
                i ++;
            }
            
        }
    }
    printf("%d %d ", countCmpOps, countSwaps);
    return;
}