Comb sort tương tự như phân loại bong bóng và phân loại cocktail. Sắp xếp lược không bắt đầu xem xét các phần tử liền kề mà thay vào đó xem xét các phần tử cách nhau một số chỉ mục nhất định, đây được gọi là khoảng trống. Khoảng trống được định nghĩa là [n / c] trong đó n là số phần tử và c là hệ số thu hẹp. Sau mỗi lần lặp, con số này được chống lại phép chia cho c và được xếp tầng cho đến khi cuối cùng, thuật toán đang xem xét các phần tử liền kề.
Input:53421 Output:12345
Giải thích
Sắp xếp kết hợp so sánh hai phần tử với một khoảng trống được định nghĩa là [n / c] trong đó n là số phần tử và c là hệ số thu nhỏ, tức là 1.3. Sau mỗi lần lặp, con số này được chống lại phép chia cho c và được xếp tầng cho đến khi cuối cùng, thuật toán đang xem xét các phần tử liền kề.
Ví dụ
#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;
}