#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <type_traits>
#include <vector>
unsigned predcount=0;
struct pred {
int mid;
pred(int m) : mid(m) {}
bool operator()(int d) {++predcount; return d<mid; }
};
template<bool med3>
void quicksort(std::vector<int>::iterator begin, std::vector<int>::iterator end) {
unsigned pivotindex;
unsigned count = end-begin;
if (count == 2) {
if (pred(begin[0])(begin[1]))
std::swap(begin[0], begin[1]);
return;
}
unsigned half = count/2;
if (med3) {
pred pred0(begin[0]);
pred pred2(begin[half]);
if (pred0(begin[half])) {
if (pred2(begin[count-1])) pivotindex = half;
else if (pred0(begin[count-1])) pivotindex = count-1;
else pivotindex = 0;
} else {
if (pred0(begin[count-1])) pivotindex = 0;
else if (pred2(begin[count-1])) pivotindex = count-1;
else pivotindex = half;
}
} else
pivotindex = half;
std::swap(begin[count-1], begin[pivotindex]);
std::vector<int>::iterator mid = std::partition(begin, end-1, pred(begin[count-1]));
std::swap(begin[count-1], *mid);
if (mid>begin+1)
quicksort<med3>(begin, mid);
if (end-mid>1)
quicksort<med3>(mid+1, end);
}
template<bool med3>
void test() {
static const unsigned datacount = 256;
// mid time mid pred med3 time med3 pred %time %pred
//256 .0000139206 2,124.0 .0000144973 2,195.7 100.0 100.0
//512 .0000308928 4,945.5 .0000301897 4,990.9 97.72 100.0
//1024 .0000702091 11,298.8 .0000665905 11,189.9 94.84 99.03
//10000 .0008441670 155,771.0 .0008147060 148,231.0 96.51 95.16
//100000 .0105284000 2,025,500.0 .0100260000 1,880,070.0 95.23 92.82
//1048576 .1347890000 26,806,400.0 .1289490000 24,518,300.0 95.67 91.46
clock_t elapsed = 0;
std::vector<int> data(datacount);
for(unsigned i=0; i<datacount; ++i)
data[i] = i;
std::cout << "med3 = " << med3 << " test:\n";
srand(0);
elapsed = 0;
unsigned loopcount=0;
predcount = 0;
do {
std::random_shuffle(data.begin(), data.end());
clock_t start = clock();
quicksort<med3>(data.begin(), data.end());
clock_t stop = clock();
assert(std::is_sorted(data.begin(), data.end(), std::less<int>()));
if (loopcount != 0)
elapsed += (stop-start);
++loopcount;
} while(elapsed < CLOCKS_PER_SEC*5);
--loopcount;
std::cout << "took " << elapsed << " ticks to do " << loopcount << " runs at " << CLOCKS_PER_SEC << "t/s.";
std::cout << "(average: " << double(elapsed)/loopcount/CLOCKS_PER_SEC << "s)\n";
std::cout << "used " << predcount << " comparisons over " << loopcount << " runs (average: " << double(predcount)/loopcount << "p)\n";
}
int main() {
test<false>();
test<true>();
return 0;
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGNhc3NlcnQ+CiNpbmNsdWRlIDxmdW5jdGlvbmFsPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxjc3RkbGliPgojaW5jbHVkZSA8Y3RpbWU+CiNpbmNsdWRlIDx0eXBlX3RyYWl0cz4KI2luY2x1ZGUgPHZlY3Rvcj4KCnVuc2lnbmVkIHByZWRjb3VudD0wOwpzdHJ1Y3QgcHJlZCB7CglpbnQgbWlkOwoJcHJlZChpbnQgbSkgOiBtaWQobSkge30KCWJvb2wgb3BlcmF0b3IoKShpbnQgZCkgeysrcHJlZGNvdW50OyByZXR1cm4gZDxtaWQ7IH0KfTsKCnRlbXBsYXRlPGJvb2wgbWVkMz4Kdm9pZCBxdWlja3NvcnQoc3RkOjp2ZWN0b3I8aW50Pjo6aXRlcmF0b3IgYmVnaW4sIHN0ZDo6dmVjdG9yPGludD46Oml0ZXJhdG9yIGVuZCkgewoJdW5zaWduZWQgcGl2b3RpbmRleDsKCXVuc2lnbmVkIGNvdW50ID0gZW5kLWJlZ2luOwoJaWYgKGNvdW50ID09IDIpIHsKCQlpZiAocHJlZChiZWdpblswXSkoYmVnaW5bMV0pKQoJCQlzdGQ6OnN3YXAoYmVnaW5bMF0sIGJlZ2luWzFdKTsKCQlyZXR1cm47Cgl9Cgl1bnNpZ25lZCBoYWxmID0gY291bnQvMjsKCWlmIChtZWQzKSB7CgkJcHJlZCBwcmVkMChiZWdpblswXSk7CgkJcHJlZCBwcmVkMihiZWdpbltoYWxmXSk7CgkJaWYgKHByZWQwKGJlZ2luW2hhbGZdKSkgewoJCQlpZiAocHJlZDIoYmVnaW5bY291bnQtMV0pKSBwaXZvdGluZGV4ID0gaGFsZjsKCQkJZWxzZSBpZiAocHJlZDAoYmVnaW5bY291bnQtMV0pKSBwaXZvdGluZGV4ID0gY291bnQtMTsKCQkJZWxzZSBwaXZvdGluZGV4ID0gMDsKCQl9IGVsc2UgewoJCQlpZiAocHJlZDAoYmVnaW5bY291bnQtMV0pKSBwaXZvdGluZGV4ID0gMDsKCQkJZWxzZSBpZiAocHJlZDIoYmVnaW5bY291bnQtMV0pKSBwaXZvdGluZGV4ID0gY291bnQtMTsKCQkJZWxzZSBwaXZvdGluZGV4ID0gaGFsZjsKCQl9Cgl9IGVsc2UKCQlwaXZvdGluZGV4ID0gaGFsZjsKCXN0ZDo6c3dhcChiZWdpbltjb3VudC0xXSwgYmVnaW5bcGl2b3RpbmRleF0pOwoJc3RkOjp2ZWN0b3I8aW50Pjo6aXRlcmF0b3IgbWlkID0gc3RkOjpwYXJ0aXRpb24oYmVnaW4sIGVuZC0xLCBwcmVkKGJlZ2luW2NvdW50LTFdKSk7CglzdGQ6OnN3YXAoYmVnaW5bY291bnQtMV0sICptaWQpOwoJaWYgKG1pZD5iZWdpbisxKQoJCXF1aWNrc29ydDxtZWQzPihiZWdpbiwgbWlkKTsKCWlmIChlbmQtbWlkPjEpCgkJcXVpY2tzb3J0PG1lZDM+KG1pZCsxLCBlbmQpOwp9Cgp0ZW1wbGF0ZTxib29sIG1lZDM+CnZvaWQgdGVzdCgpIHsKCXN0YXRpYyBjb25zdCB1bnNpZ25lZCBkYXRhY291bnQgPSAyNTY7CgkvLyAgICAgICAgICAgIG1pZCB0aW1lICAgICAgbWlkIHByZWQgICAgbWVkMyB0aW1lICAgICBtZWQzIHByZWQgICV0aW1lICAlcHJlZAoJLy8yNTYgICAgICAuMDAwMDEzOTIwNiAgICAgICAyLDEyNC4wICAuMDAwMDE0NDk3MyAgICAgICAyLDE5NS43ICAxMDAuMCAgMTAwLjAKCS8vNTEyICAgICAgLjAwMDAzMDg5MjggICAgICAgNCw5NDUuNSAgLjAwMDAzMDE4OTcgICAgICAgNCw5OTAuOSAgOTcuNzIgIDEwMC4wCgkvLzEwMjQgICAgIC4wMDAwNzAyMDkxICAgICAgMTEsMjk4LjggIC4wMDAwNjY1OTA1ICAgICAgMTEsMTg5LjkgIDk0Ljg0ICA5OS4wMwoJLy8xMDAwMCAgICAuMDAwODQ0MTY3MCAgICAgMTU1LDc3MS4wICAuMDAwODE0NzA2MCAgICAgMTQ4LDIzMS4wICA5Ni41MSAgOTUuMTYKCS8vMTAwMDAwICAgLjAxMDUyODQwMDAgICAyLDAyNSw1MDAuMCAgLjAxMDAyNjAwMDAgICAxLDg4MCwwNzAuMCAgOTUuMjMgIDkyLjgyCgkvLzEwNDg1NzYgIC4xMzQ3ODkwMDAwICAyNiw4MDYsNDAwLjAgIC4xMjg5NDkwMDAwICAyNCw1MTgsMzAwLjAgIDk1LjY3ICA5MS40NgoJY2xvY2tfdCBlbGFwc2VkID0gMDsKCXN0ZDo6dmVjdG9yPGludD4gZGF0YShkYXRhY291bnQpOwoJZm9yKHVuc2lnbmVkIGk9MDsgaTxkYXRhY291bnQ7ICsraSkKCQlkYXRhW2ldID0gaTsKCXN0ZDo6Y291dCA8PCAibWVkMyA9ICIgPDwgbWVkMyA8PCAiIHRlc3Q6XG4iOwoKCXNyYW5kKDApOwoJZWxhcHNlZCA9IDA7Cgl1bnNpZ25lZCBsb29wY291bnQ9MDsKCXByZWRjb3VudCA9IDA7CglkbyB7CgkJc3RkOjpyYW5kb21fc2h1ZmZsZShkYXRhLmJlZ2luKCksIGRhdGEuZW5kKCkpOwoJCWNsb2NrX3Qgc3RhcnQgPSBjbG9jaygpOwoJCXF1aWNrc29ydDxtZWQzPihkYXRhLmJlZ2luKCksIGRhdGEuZW5kKCkpOwoJCWNsb2NrX3Qgc3RvcCA9IGNsb2NrKCk7CgkJYXNzZXJ0KHN0ZDo6aXNfc29ydGVkKGRhdGEuYmVnaW4oKSwgZGF0YS5lbmQoKSwgc3RkOjpsZXNzPGludD4oKSkpOwoJCWlmIChsb29wY291bnQgIT0gMCkKCQkJZWxhcHNlZCArPSAoc3RvcC1zdGFydCk7CgkJKytsb29wY291bnQ7Cgl9IHdoaWxlKGVsYXBzZWQgPCBDTE9DS1NfUEVSX1NFQyo1KTsKCS0tbG9vcGNvdW50OwoJc3RkOjpjb3V0IDw8ICJ0b29rICIgPDwgZWxhcHNlZCA8PCAiIHRpY2tzIHRvIGRvICIgPDwgbG9vcGNvdW50IDw8ICIgcnVucyBhdCAiIDw8IENMT0NLU19QRVJfU0VDIDw8ICJ0L3MuIjsKCXN0ZDo6Y291dCA8PCAiKGF2ZXJhZ2U6ICIgPDwgZG91YmxlKGVsYXBzZWQpL2xvb3Bjb3VudC9DTE9DS1NfUEVSX1NFQyA8PCAicylcbiI7CglzdGQ6OmNvdXQgPDwgInVzZWQgIiA8PCBwcmVkY291bnQgPDwgIiBjb21wYXJpc29ucyBvdmVyICIgPDwgbG9vcGNvdW50IDw8ICIgcnVucyAoYXZlcmFnZTogIiA8PCBkb3VibGUocHJlZGNvdW50KS9sb29wY291bnQgPDwgInApXG4iOwp9CgppbnQgbWFpbigpIHsKCXRlc3Q8ZmFsc2U+KCk7Cgl0ZXN0PHRydWU+KCk7CiAgICByZXR1cm4gMDsKfQ==