#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
int swapCount = 0;
class X
{
public:
int x;
X( int val ): x( val ) {};
friend void swap( X &a, X &b )
{
using std::swap;
swap( a.x, b.x );
swapCount++;
std::cout << "a.x = " << a.x << ", b.x = " << b.x << std::endl;
}
};
void f(int n) {
std::vector<X> vec;
for ( int i = 0; i < n; i++ )
vec.push_back( X( rand() % 1000 ) );
swapCount = 0;
std::stable_sort( vec.begin(), vec.end(),
[] ( const X &a, const X &b ) -> bool { return (a.x) > (b.x); } );
/*for(auto v : vec)
std::cout << v.x << ", ";
std::cout << std::endl;*/
std::cout << n << ") " << "swapCount=" << swapCount << "\n";
}
int main() {
//for(int n=1; n<100; ++n) f(n);
f(50000000);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8c3RkbGliLmg+CgppbnQgc3dhcENvdW50ID0gMDsKCmNsYXNzIFgKewpwdWJsaWM6CglpbnQgeDsKCQoJWCggaW50IHZhbCApOiB4KCB2YWwgKSB7fTsKCQoJZnJpZW5kIHZvaWQgc3dhcCggWCAmYSwgWCAmYiApCgl7CgkJdXNpbmcgc3RkOjpzd2FwOwoJCXN3YXAoIGEueCwgYi54ICk7CgkJc3dhcENvdW50Kys7CgkJc3RkOjpjb3V0IDw8ICJhLnggPSAiIDw8IGEueCA8PCAiLCBiLnggPSAiIDw8IGIueCA8PCBzdGQ6OmVuZGw7Cgl9Cn07Cgp2b2lkIGYoaW50IG4pIHsKCXN0ZDo6dmVjdG9yPFg+IHZlYzsKCWZvciAoIGludCBpID0gMDsgaSA8IG47IGkrKyApIAoJCXZlYy5wdXNoX2JhY2soIFgoIHJhbmQoKSAlIDEwMDAgKSApOwoKCXN3YXBDb3VudCA9IDA7CglzdGQ6OnN0YWJsZV9zb3J0KCB2ZWMuYmVnaW4oKSwgdmVjLmVuZCgpLCAKCQlbXSAoIGNvbnN0IFggJmEsIGNvbnN0IFggJmIgKSAtPiBib29sIHsgcmV0dXJuIChhLngpID4gKGIueCk7IH0gKTsKCQkKCS8qZm9yKGF1dG8gdiA6IHZlYykKCQlzdGQ6OmNvdXQgPDwgdi54IDw8ICIsICI7CglzdGQ6OmNvdXQgPDwgc3RkOjplbmRsOyovCgkJCglzdGQ6OmNvdXQgPDwgbiA8PCAiKSAiIDw8ICJzd2FwQ291bnQ9IiA8PCBzd2FwQ291bnQgPDwgIlxuIjsKfQoKaW50IG1haW4oKSB7CgkvL2ZvcihpbnQgbj0xOyBuPDEwMDsgKytuKSBmKG4pOwoJZig1MDAwMDAwMCk7CglyZXR1cm4gMDsKfQ==