빗 정렬은 거품 정렬 및 칵테일 정렬과 유사합니다. 콤 정렬은 인접한 요소를 살펴보는 것으로 시작하지 않고 대신 특정 인덱스 수만큼 떨어져 있는 요소를 살펴봅니다. 이를 간격이라고 합니다. 간격은 [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; }