#include <iostream>

using namespace std;
int comparisons=0,swaps=0;
int*CombSort(int*input,int input_size){
    int gap=input_size;
    double shrink=1.3;
    bool swapped;
    while (!( gap==1 and swapped==false )){//repeate until gap==1 and swapped==false
        gap=int(gap/shrink);
        if(gap<1)
        {
            gap=1;
        }//end if
        int i=0;
        swapped=false;
        while(!(    i+gap>=input_size    )){
        	comparisons++;
            if(input[i]>input[i+gap]){
                swap(input[i],input[i+gap]);
                swaps++;
                swapped=true;
            }//end if
            i=i+1;
        }//end while
    }//end while
    return input;
}//end combSort
int main()
{
    int A[10]={10,2,3,4,5,6,7,8,9,1};
    for(int i=0;i<10;i++)
        cout<<A[i]<<" ";
    cout<<endl;
    CombSort(A,10);
    cout<<"comparsisons="<<comparisons<<" swaps="<<swaps<<endl;
    for(int i=0;i<10;i++)
        cout<<A[i]<<" ";
    cout<<endl;
    return 0;
}