#include <iostream>
#include <chrono>
#include <algorithm>
#include <cstdlib>
using namespace std;
std::vector<int> generate()
{
std::vector<int> vec(1500000);
std::generate (vec.begin(), vec.end(), rand);
std::transform(vec.begin(), vec.end(), vec.begin(),
std::bind2nd(std::modulus<int>(), 1000));
return std::move(vec);
}
int cmp(const void *a, const void *b)
{
return (*(int*)a) - (*(int*)b);
}
template<class F>
void measurement_time(F f)
{
auto vec = generate();
auto start = std::chrono::high_resolution_clock::now();
f(vec);
auto stop = std::chrono::high_resolution_clock::now();
std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(stop - start).count() << "ms" << std::endl;
}
int main(int argc, char *argv[])
{
for(int i = 0; i < 10; ++i)
{
measurement_time([](std::vector<int>& vec)
{
std::sort(vec.begin(), vec.end());
});
measurement_time([](std::vector<int>& vec)
{
qsort(&vec[0], vec.size(), sizeof(int), cmp);
});
std::cout << std::endl;
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y2hyb25vPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Y3N0ZGxpYj4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnN0ZDo6dmVjdG9yPGludD4gZ2VuZXJhdGUoKQp7CglzdGQ6OnZlY3RvcjxpbnQ+IHZlYygxNTAwMDAwKTsKIAogICAgc3RkOjpnZW5lcmF0ZSAodmVjLmJlZ2luKCksIHZlYy5lbmQoKSwgcmFuZCk7CiAgICBzdGQ6OnRyYW5zZm9ybSh2ZWMuYmVnaW4oKSwgdmVjLmVuZCgpLCB2ZWMuYmVnaW4oKSwKICAgICAgICAgICAgICAgICAgIHN0ZDo6YmluZDJuZChzdGQ6Om1vZHVsdXM8aW50PigpLCAxMDAwKSk7CiAgICByZXR1cm4gc3RkOjptb3ZlKHZlYyk7Cn0KCmludCBjbXAoY29uc3Qgdm9pZCAqYSwgY29uc3Qgdm9pZCAqYikKewoJcmV0dXJuICgqKGludCopYSkgLSAoKihpbnQqKWIpOwp9Cgp0ZW1wbGF0ZTxjbGFzcyBGPgp2b2lkIG1lYXN1cmVtZW50X3RpbWUoRiBmKQp7CglhdXRvIHZlYyA9IGdlbmVyYXRlKCk7CglhdXRvIHN0YXJ0ID0gc3RkOjpjaHJvbm86OmhpZ2hfcmVzb2x1dGlvbl9jbG9jazo6bm93KCk7CiAgICBmKHZlYyk7CiAgICBhdXRvIHN0b3AgPSBzdGQ6OmNocm9ubzo6aGlnaF9yZXNvbHV0aW9uX2Nsb2NrOjpub3coKTsKICAgIHN0ZDo6Y291dCA8PCBzdGQ6OmNocm9ubzo6ZHVyYXRpb25fY2FzdDxzdGQ6OmNocm9ubzo6bWlsbGlzZWNvbmRzPihzdG9wIC0gc3RhcnQpLmNvdW50KCkgPDwgIm1zIiA8PCBzdGQ6OmVuZGw7Cn0KCmludCBtYWluKGludCBhcmdjLCBjaGFyICphcmd2W10pCnsKCWZvcihpbnQgaSA9IDA7IGkgPCAxMDsgKytpKQoJewoJICAgIG1lYXN1cmVtZW50X3RpbWUoW10oc3RkOjp2ZWN0b3I8aW50PiYgdmVjKQoJICAgIHsKCSAgICAJc3RkOjpzb3J0KHZlYy5iZWdpbigpLCB2ZWMuZW5kKCkpOwoJICAgIH0pOwoJICAgIAoJICAgIG1lYXN1cmVtZW50X3RpbWUoW10oc3RkOjp2ZWN0b3I8aW50PiYgdmVjKQoJICAgIHsKCSAgICAJcXNvcnQoJnZlY1swXSwgdmVjLnNpemUoKSwgc2l6ZW9mKGludCksIGNtcCk7CgkgICAgfSk7CgkgICAgCgkgICAgc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKCX0KfQ==