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

Comb Sort là cải tiến của Bubble Sort. Bubble Sort so sánh phần tử liền kề (gap=1). Comb Sort so sánh với khoảng cách (gap) lớn, sau đó thu hẹp gap dần. Hệ số thu hẹp (shrink factor) = 1.3.

Thuật toán

CombSort(array, size):
    gap = size
    flag = true
    while gap != 1 OR flag == true:
        gap = floor(gap / 1.3)
        if gap < 1: gap = 1
        flag = false
        for i = 0 to size - gap - 1:
            if array[i] > array[i+gap]:
                swap(array[i], array[i+gap])
                flag = true
        end for
    end while
end

Code ví dụ

#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) {
        gap = (gap * 10) / 13;  // gap = floor(gap/1.3) tránh float
        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 << "Nhap so phan tu: ";
    cin >> n;
    int arr[n];
    
    cout << "Nhap cac phan tu:\n";
    for(int i = 0; i < n; i++) cin >> arr[i];
    
    cout << "Truoc sap xep: "; display(arr, n);
    combSort(arr, n);
    cout << "Sau sap xep:  "; display(arr, n);
}

Kết quả mẫu

Nhap so phan tu: 10
Nhap cac phan tu: 108 96 23 74 12 56 85 42 13 47
Truoc sap xep: 108 96 23 74 12 56 85 42 13 47
Sau sap xep:  12 13 23 42 47 56 74 85 96 108

Độ phức tạp

• Tốt nhất: O(n log n) (gần như đã sắp xếp).
• Trung bình: O(n²/2^p) với p là số lần tăng gap.
• Xấu nhất: O(n²).
• Không gian: O(1).
• Ổn định: Không (do swap khoảng cách lớn).

Tại sao shrink factor = 1.3?

Kết quả thực nghiệm: 1.3 cho hiệu suất tốt nhất. Giá trị nhỏ hơn → nhiều pass hơn. Giá trị lớn hơn → bỏ sót nhiều inversion.