C++로 구현하는 콤 정렬(Comb Sort) 프로그램

콤 정렬(Comb Sort)은 버블 정렬(Bubble Sort)과 칵테일 정렬(Cocktail Sort)과 유사한 정렬 알고리즘입니다. 다만 일반적인 버블 정렬과 달리, 콤 정렬은 처음부터 인접한 요소를 비교하지 않고 일정한 간격(gap)만큼 떨어져 있는 요소들을 먼저 비교한다는 점이 특징입니다.

이 간격은 [n/c]로 정의됩니다. 여기서 n은 배열에 담긴 요소의 개수, c는 축소 계수(shrink factor)입니다. 매 반복(iteration)이 끝날 때마다 간격 값을 c로 다시 나누고 소수점 이하는 버리면서 점차 줄여 나가고, 결국 간격이 1이 되어 인접한 요소끼리 비교하는 단계에 도달하면 정렬이 완료됩니다.

입력: 5 3 4 2 1
출력: 1 2 3 4 5

동작 원리

콤 정렬은 [n/c]로 계산된 간격을 기준으로 두 요소를 비교합니다. 여기서 n은 요소의 총개수이고, c는 축소 계수로 일반적으로 1.3을 사용합니다. 매 반복이 끝날 때마다 간격을 c로 나눈 뒤 내림하여 갱신하고, 이 과정을 간격이 1이 되어 인접한 요소들을 비교할 때까지 반복합니다.

간격이 9 또는 10이 될 때 11로 강제 조정하는 규칙(rule of 11)을 적용하면 성능이 더 향상되는 것으로 알려져 있습니다. 콤 정렬의 평균 시간 복잡도는 O(n²)이지만, 실제 동작에서는 거북목(turtle) 문제를 완화하기 때문에 버블 정렬보다 훨씬 빠른 속도를 보여줍니다.

예제 코드

#include <iostream>
using namespace std;
void combsort(int a[], int n) {
    int i, j, gap, swapped = 1;
    double temp;
    gap = n;
    while (gap > 1 || swapped == 1) {
        gap = gap * 10 / 1.3;
        if (gap == 9 || gap == 10) {
            gap = 11;
        }
        if (gap < 1) {
            gap = 1;
        }
        swapped = 0;
        for (i = 0, j = gap; j < n; i++, j++) {
            if (a[i] > a[j]) {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                swapped = 1;
            }
        }
    }
}
int main () {
    int n, i;
    int arr[] = { 5, 3, 4, 2, 1 };
    n=5;
    combsort(arr, n);
    for(i = 0;i < n;i++) {
        cout<<arr[i]<<"\t";
    }
    return 0;
}

위 코드는 크기가 5인 배열 {5, 3, 4, 2, 1}을 콤 정렬로 오름차순 정렬한 후, 결과값 1 2 3 4 5를 탭으로 구분하여 출력합니다. 코드에서는 간격을 1.3으로 나누어 줄여 가며 전체 배열을 순회하고, 교환이 발생했는지를 나타내는 swapped 플래그를 통해 정렬 완료 여부를 판단합니다.