C++로 구현하는 콤 정렬(Comb Sort) 완벽 가이드

콤 정렬(Comb Sort)과 버블 정렬(Bubble Sort)의 기본 아이디어는 동일합니다. 즉, 콤 정렬은 버블 정렬을 개선한 알고리즘이라고 할 수 있습니다.

버블 정렬에서는 각 단계마다 인접한 두 요소를 비교하지만, 콤 정렬에서는 일정한 간격(gap)을 두고 떨어져 있는 요소들을 비교합니다. 한 단계가 끝날 때마다 이 간격을 점차 줄여 나가며, 감소 계수(축소 계수, shrink factor)는 1.3입니다. 다시 말해, 각 단계가 완료될 때마다 간격을 1.3으로 나눈 값으로 갱신합니다.

시간 복잡도는 최선의 경우 O(n log n), 평균의 경우 O(n²/2ⁿᴾ)(p는 증분 횟수), 최악의 경우 O(n²)입니다.

알고리즘

CombSort(array, size)

입력 − 데이터 배열과 배열의 전체 크기

출력 − 정렬된 배열

Begin
    gap := size
    flag := true
    while the gap ≠ 1 OR flag = true do
        gap = floor(gap/1.3) // 나눗셈 후 내림값 계산
        if gap < 1 then
            gap := 1
        flag = false
        for i := 0 to size – gap - 1 do
            if array[i] > array[i+gap] then
                swap array[i] with array[i+gap]
                flag = true;
        done
    done
End

C++ 구현 예제

아래는 C++로 작성한 콤 정렬의 전체 코드입니다. 사용자로부터 배열 크기와 요소를 입력받아 정렬 전후의 배열 상태를 출력합니다.

#include<iostream>
#include<algorithm>
using namespace std;

void display(int *array, int size){
    for(int i = 0; i<size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void combSort(int *array, int size){
    int gap = size; // 간격을 배열 크기로 초기화
    bool flag = true;
    while(gap != 1 || flag == true){
        gap = (gap*10)/13; // 축소 계수로 간격 줄이기
        if(gap<1)
            gap = 1;
        flag = false;
        for(int i = 0; i<size-gap; i++){ // 간격만큼 떨어진 요소 비교
            if(array[i] > array[i+gap]){
                swap(array[i], array[i+gap]);
                flag = true;
            }
        }
    }
}

int main(){
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n]; // 입력받은 크기의 배열 생성
    cout << "Enter elements:" << endl;
    for(int i = 0; i<n; i++){
        cin >> arr[i];
    }
    cout << "Array before Sorting: ";
    display(arr, n);
    combSort(arr, n);
    cout << "Array after Sorting: ";
    display(arr, n);
}

실행 결과

Enter the number of elements: 10
Enter elements:
108 96 23 74 12 56 85 42 13 47
Array before Sorting: 108 96 23 74 12 56 85 42 13 47
Array after Sorting: 12 13 23 42 47 56 74 85 96 108

정리

콤 정렬은 버블 정렬의 가장 큰 약점인 '거북이(turtle)' 문제, 즉 배열 끝에 있는 작은 값들이 앞으로 이동하는 데 오래 걸리는 현상을 간격(gap) 개념으로 해결한 알고리즘입니다. 구현이 간단하면서도 실제 데이터에서 버블 정렬보다 훨씬 빠른 성능을 보여주기 때문에, 정렬 알고리즘 학습 시 좋은 비교 대상이 됩니다.