빗 정렬은 거품 정렬 및 칵테일 정렬과 유사합니다. 콤 정렬은 인접한 요소를 살펴보는 것으로 시작하지 않고 대신 특정 인덱스 수만큼 떨어져 있는 요소를 살펴봅니다. 이를 간격이라고 합니다. 간격은 [n/c]로 정의되며, 여기서 n은 요소 수이고 c는 축소 계수입니다. 각 반복 후에 이 숫자는 c로 나누어지고 결국 알고리즘이 인접한 요소를 볼 때까지 내림됩니다.
Input:53421 Output:12345
설명
콤 정렬은 [n/c]로 정의되는 간격이 있는 두 요소를 비교합니다. 여기서 n은 요소 수이고 c는 축소 계수(즉, 1.3)입니다. 각 반복 후에 이 숫자는 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 / 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;
}