#include <iostream>
#include <vector>
#include <chrono>
using namespace std;

struct Timer {
    std::chrono::high_resolution_clock::time_point start;
    Timer() : start(std::chrono::high_resolution_clock::now()) {}
    ~Timer() {
        auto stop = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
        std::cout << "Time: " << duration.count() << " ms\n";
    }
};
template<typename T>

void Firstalg(T x[], int &a, int &b, int n){
	a=0;
	b=0;
	for(int i=0;i<n;i++){
		for(int j=0; j<n-i-1; j++){
			a+=1;
			if(x[j]>x[j+1]){
				swap(x[j],x[j+1]);
				b+=1;
			}
		}
	}
}

template<typename T>
void Secondalg(T &x, int &a, int &b, int n){
	a=0;
	b=0;
	for(int i=1; i<n; i++){
		int key = x[i];
		int j=i-1;
		while(j>=0){
			a+=1;
			if(x[j]>key){
			x[j+1]=x[j];
			b+=1;
			j--;
			}else{break;}
		}
		x[j+1]=key;
	}
}

int main() {
	int sort, comp;
	int n = 10000;
	int x[n];
	for (int i=0; i<n; i++){
		x[i]=rand() % 10001;
	};
	
	for (int i=0; i<100; i++){
		cout<<x[i]<<" ";
	};
	cout<<endl;
	{
		Timer t;
		Firstalg(x,sort,comp,n);
	}
	
}		
/*	Secondalg(x,sort,comp,n);
	for (int i=0; i<n; i++){
		cout<<x[i]<<" ";
	};
	cout<<endl;
	cout<<"Кількість порівнянь "<<sort<<endl<<"Кількість перестановок "<<comp;
	
	Firstalg(x,sort,comp,n);
	for (int i=0; i<n; i++){
		cout<<x[i]<<" ";
	};
	cout<<endl;
	cout<<"Кількість порівнянь "<<sort<<endl<<"Кількість перестановок "<<comp;*/