#include <iostream>
#include <vector>
#include <random>
#include <chrono>

//documet from ttp://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%A0%E3%82%BD%E3%83%BC%E3%83%88

std::vector<int> MakeData(std::size_t N){
	std::random_device rd;
	std::mt19937 mt(rd());
	std::uniform_int_distribution<> uid;
	std::vector<int> ret;

	for (std::size_t i = 0; i < N; i++){
		ret.push_back(uid(mt));
	}

	return ret;
}

bool BubbleSort(std::vector<int>& vec){
	for (std::size_t i = 0; i < vec.size(); i++){
		for (std::size_t j = i + 1; j < vec.size(); j++){//maybe this is best speed of bubble sort.but has value line limited issue for large value.
			if (vec[i] < vec[j])std::swap(vec[i], vec[j]);
		}
	}
	return true;
}

bool CombSort(std::vector<int>& vec){
	std::size_t h = vec.size();
	bool IsSwap = false;

	while (h>1 || IsSwap){
		IsSwap = false;
		if (h > 1) h=(h * 10) / 13;
		for (int i = 0; i < vec.size() - h; i++){
			if (vec[i] < vec[i + h]){
				std::swap(vec[i], vec[i + h]);
				IsSwap = true;
			}
		}
	}
	return true;
}

int main(){

	//static const std::size_t N = 3000;//this number is use about 1sec in bubule sort for my pc.
	static const std::size_t N =25000;
	auto r1 = MakeData(N);
	auto r2 = r1;

	auto S1 = std::chrono::system_clock::now();
	BubbleSort(r1);
	auto E1 = std::chrono::system_clock::now();

	auto Eli1 = std::chrono::duration_cast <std::chrono::milliseconds>(E1 - S1);

	auto S2 = std::chrono::system_clock::now();
	CombSort(r2);
	auto E2 = std::chrono::system_clock::now();

	auto Eli2 = std::chrono::duration_cast <std::chrono::milliseconds>(E2 - S2);

	std::cout << "bubble sort:" << Eli1.count() << "ms" << std::endl;
	std::cout << "comb sort:" << Eli2.count() << "ms" << std::endl;//oh fast!

	bool F = false;

	for (std::size_t i = 0; i < N; i++)	{
		F = r1[i] == r2[i];
		if (F == false) break;
	}

	std::cout << "this is " << (F ? "Valid." : "Invalid.") << std::endl;

	return 0;
}