Thuật toán Comb Sort (Sắp xếp chải)

Ý tưởng cơ bản của Comb Sort và Bubble Sort giống nhau. Comb Sort là cải tiến của Bubble Sort. Bubble Sort so sánh phần tử liền kề, Comb Sort so sánh với khoảng cách (gap) cụ thể. Sau mỗi phase, gap giảm dần với hệ số co (shrink factor) 1.3.

Độ phức tạp Comb Sort

• Time Complexity: O(n log n) tốt nhất, O(n²/2^p) trung bình (p = số lần tăng), O(n²) xấu nhất
• Space Complexity: O(1)

Input và Output

Input: Danh sách chưa sắp xếp: 108 96 23 74 12 56 85 42 13 47
Output: Mảng trước sắp xếp: 108 96 23 74 12 56 85 42 13 47
Mảng sau sắp xếp: 12 13 23 42 47 56 74 85 96 108

Thuật toán

CombSort(array, size)
Input: Mảng dữ liệu, tổng số phần tử
Output: Mảng đã sắp xếp

Begin
  gap := size
  flag := true
  while 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
  done
End

Ví dụ (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) {
        gap = (gap * 10) / 13; // chia 1.3
        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 << "Nhập số phần tử: "; cin >> n;
    int arr[n];
    cout << "Nhập phần tử:" << endl;
    for(int i = 0; i < n; i++) cin >> arr[i];
    cout << "Trước sắp xếp: "; display(arr, n);
    combSort(arr, n);
    cout << "Sau sắp xếp: "; display(arr, n);
}

Kết quả

Nhập số phần tử: 10
Nhập phần tử: 108 96 23 74 12 56 85 42 13 47
Trước sắp xếp: 108 96 23 74 12 56 85 42 13 47
Sau sắp xếp: 12 13 23 42 47 56 74 85 96 108

Đặc điểm: Comb Sort cải tiến Bubble Sort bằng cách loại bỏ "rùa" (phần tử nhỏ ở cuối) nhanh hơn nhờ gap lớn ban đầu. Hệ số 1.3 được chọn thực nghiệm. Không ổn định.