Chương trình C++ thuật toán Comb Sort

Comb Sort tương tự Bubble Sort và Cocktail Sort. Khác ở chỗ không bắt đầu so sánh phần tử liền kề mà so sánh các phần tử cách nhau một khoảng (gap). Gap = [n/c] với n số phần tử, c là hệ số thu hẹp (shrink factor). Sau mỗi lần lặp, gap chia cho c và làm tròn xuống cho đến khi gap = 1 (so sánh liền kề).

Ví dụ

Input: 5 3 4 2 1 
Output: 1 2 3 4 5

Giải thích

Comb Sort so sánh hai phần tử cách nhau gap = [n/c], c=1.3. Sau mỗi vòng lặp, gap /= c và floor cho đến khi gap=1 (trở thành Bubble Sort).

Ví dụ mã C++

#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 / 13; // gap /= 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 = 5; 
    int arr[] = {5, 3, 4, 2, 1}; 
    combsort(arr, n); 
    for (int i = 0; i < n; i++) 
        cout << arr[i] << "\t"; 
    return 0; 
}