#include <iostream>
#include <cstdlib>
#include <ctime>
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[1000];
    srand(time(0));
    for(int i=0;i<1000;i++)
    	A[i]=rand();
      //  cout<<A[i]<<" ";
    //cout<<endl;
    CombSort(A,1000);
    cout<<"comparsisons="<<comparisons<<" swaps="<<swaps<<endl;
    //for(int i=0;i<10;i++)
      //  cout<<A[i]<<" ";
    //cout<<endl;
    return 0;
}