#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <stdint.h>
#include <sys/time.h>
#define ELEMS 10000000
#define TOPSS 1000
typedef double val_t;
inline static double baka_sec_count(void) {
struct timeval tv;
gettimeofday(&tv, NULL);
return (double)tv.tv_sec + ((double)tv.tv_usec / 1000000.0);
}
inline static uint32_t rand32() {
static uint32_t y = 2463534242;
y = y ^ (y << 13);
y = y ^ (y >> 17);
return y = y ^ (y << 15);
}
inline static uint64_t rand64(void) {
static uint64_t x = 88172645463325252ULL;
x = x ^ (x << 13);
x = x ^ (x >> 7);
return x = x ^ (x << 17);
}
inline static val_t* alloc_data(int n_) {
val_t
* p
= (val_t
*)malloc(sizeof(val_t
) * n_
);
for (int i = 0; i < n_; ++i) {
p[i] = rand64();
}
return p;
}
inline static val_t* alloc_saiaku_data(int n_) {
val_t
* p
= (val_t
*)malloc(sizeof(val_t
) * n_
);
for (int i = 0; i < n_ / 2 ; ++i) {
p[i] = i;
}
for (int i = n_ / 2; i < n_; ++i) {
p[i] = n_ - i;
}
return p;
}
inline static void free_data(double* p_) {
}
inline static val_t* partition(val_t* p_left_, val_t* p_right_) {
val_t* const p_pivot = p_left_ + (rand32() % (p_right_ - p_left_));
val_t tmp;
tmp = *p_pivot; *p_pivot = *p_right_; *p_right_ = tmp;
val_t const* const p_prev_right = p_right_ - 1;
for (val_t* p = p_left_; p < p_prev_right; ++p) {
if (*p > *p_right_) {
tmp = *p; *p = *p_left_; *p_left_ = tmp;
++p_left_;
}
}
tmp = *p_right_; *p_right_ = *p_left_; *p_left_ = tmp;
return p_left_;
}
inline static void quickselect(val_t* p_left_, val_t* p_right_, val_t* k_) {
while (p_left_ < p_right_) {
val_t* p_pivot = partition(p_left_, p_right_);
if (p_pivot > k_) {
p_right_ = p_pivot + 1;
} else if (p_pivot < k_) {
p_left_ = p_pivot + 1;
} else {
break;
}
}
}
int main(int argc, char* argv[])
{
val_t* p1 = alloc_data(ELEMS);
val_t* p2 = alloc_saiaku_data(ELEMS);
double s;
double e;
s = baka_sec_count();
quickselect(p1, p1 + ELEMS - 1, p1 + TOPSS - 1);
e = baka_sec_count();
fprintf(stdout
, "turnaround time ::= %.04lf sec\n", e
- s
);
s = baka_sec_count();
quickselect(p2, p2 + ELEMS - 1, p2 + TOPSS - 1);
e = baka_sec_count();
fprintf(stdout
, "turnaround time ::= %.04lf sec\n", e
- s
);
free_data(p1);
free_data(p2);
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPG1lbW9yeS5oPgojaW5jbHVkZSA8c3RkaW50Lmg+CiNpbmNsdWRlIDxzeXMvdGltZS5oPgoKI2RlZmluZSBFTEVNUyAxMDAwMDAwMAojZGVmaW5lIFRPUFNTIDEwMDAKCnR5cGVkZWYgZG91YmxlIHZhbF90OwoKaW5saW5lIHN0YXRpYyBkb3VibGUgYmFrYV9zZWNfY291bnQodm9pZCkgewogICAgc3RydWN0IHRpbWV2YWwgdHY7CiAgICBnZXR0aW1lb2ZkYXkoJnR2LCBOVUxMKTsKCXJldHVybiAoZG91YmxlKXR2LnR2X3NlYyArICgoZG91YmxlKXR2LnR2X3VzZWMgLyAxMDAwMDAwLjApOwp9CgppbmxpbmUgc3RhdGljIHVpbnQzMl90IHJhbmQzMigpIHsKCXN0YXRpYyB1aW50MzJfdCB5ID0gMjQ2MzUzNDI0MjsKCXkgPSB5IF4gKHkgPDwgMTMpOwoJeSA9IHkgXiAoeSA+PiAxNyk7CglyZXR1cm4geSA9IHkgXiAoeSA8PCAxNSk7Cn0KCmlubGluZSBzdGF0aWMgdWludDY0X3QgcmFuZDY0KHZvaWQpIHsKCXN0YXRpYyB1aW50NjRfdCB4ID0gODgxNzI2NDU0NjMzMjUyNTJVTEw7Cgl4ID0geCBeICh4IDw8IDEzKTsKCXggPSB4IF4gKHggPj4gNyk7CglyZXR1cm4geCA9IHggXiAoeCA8PCAxNyk7Cn0KCmlubGluZSBzdGF0aWMgdmFsX3QqIGFsbG9jX2RhdGEoaW50IG5fKSB7Cgl2YWxfdCogcCA9ICh2YWxfdCopbWFsbG9jKHNpemVvZih2YWxfdCkgKiBuXyk7CgoJZm9yIChpbnQgaSA9IDA7IGkgPCBuXzsgKytpKSB7CgkJcFtpXSA9IHJhbmQ2NCgpOwoJfQoKCXJldHVybiBwOwp9CgppbmxpbmUgc3RhdGljIHZhbF90KiBhbGxvY19zYWlha3VfZGF0YShpbnQgbl8pIHsKCXZhbF90KiBwID0gKHZhbF90KiltYWxsb2Moc2l6ZW9mKHZhbF90KSAqIG5fKTsKCglmb3IgKGludCBpID0gMDsgaSA8IG5fIC8gMiA7ICsraSkgewoJCXBbaV0gPSBpOwoJfQoJZm9yIChpbnQgaSA9IG5fIC8gMjsgaSA8IG5fOyArK2kpIHsKCQlwW2ldID0gbl8gLSBpOwoJfQoKCXJldHVybiBwOwp9CgppbmxpbmUgc3RhdGljIHZvaWQgZnJlZV9kYXRhKGRvdWJsZSogcF8pIHsKCWZyZWUocF8pOwp9CgppbmxpbmUgc3RhdGljIHZhbF90KiBwYXJ0aXRpb24odmFsX3QqIHBfbGVmdF8sIHZhbF90KiBwX3JpZ2h0XykgewoKCXZhbF90KiBjb25zdCBwX3Bpdm90ID0gcF9sZWZ0XyArIChyYW5kMzIoKSAlIChwX3JpZ2h0XyAtIHBfbGVmdF8pKTsKCXZhbF90IHRtcDsKCXRtcCA9ICpwX3Bpdm90OyAqcF9waXZvdCA9ICpwX3JpZ2h0XzsgKnBfcmlnaHRfID0gdG1wOwoJCgl2YWxfdCBjb25zdCogY29uc3QgcF9wcmV2X3JpZ2h0ID0gcF9yaWdodF8gLSAxOwoKCWZvciAodmFsX3QqIHAgPSBwX2xlZnRfOyBwIDwgcF9wcmV2X3JpZ2h0OyArK3ApIHsKCQlpZiAoKnAgPiAqcF9yaWdodF8pIHsKCQkJdG1wID0gKnA7ICpwID0gKnBfbGVmdF87ICpwX2xlZnRfID0gdG1wOwoJCQkrK3BfbGVmdF87CgkJfQoJfQoJdG1wID0gKnBfcmlnaHRfOyAqcF9yaWdodF8gPSAqcF9sZWZ0XzsgKnBfbGVmdF8gPSB0bXA7CglyZXR1cm4gcF9sZWZ0XzsKfQoKaW5saW5lIHN0YXRpYyB2b2lkIHF1aWNrc2VsZWN0KHZhbF90KiBwX2xlZnRfLCB2YWxfdCogcF9yaWdodF8sIHZhbF90KiBrXykgewoKCXdoaWxlIChwX2xlZnRfIDwgcF9yaWdodF8pIHsKCQl2YWxfdCogcF9waXZvdCA9IHBhcnRpdGlvbihwX2xlZnRfLCBwX3JpZ2h0Xyk7CgkJaWYgKHBfcGl2b3QgPiBrXykgewoJCQlwX3JpZ2h0XyA9IHBfcGl2b3QgKyAxOwoJCX0gZWxzZSBpZiAocF9waXZvdCA8IGtfKSB7CgkJCXBfbGVmdF8gPSBwX3Bpdm90ICsgMTsKCQl9IGVsc2UgewoJCQlicmVhazsKCQl9Cgl9Cn0KCmludCBtYWluKGludCBhcmdjLCBjaGFyKiBhcmd2W10pCnsKCXZhbF90KiBwMSA9IGFsbG9jX2RhdGEoRUxFTVMpOwoJdmFsX3QqIHAyID0gYWxsb2Nfc2FpYWt1X2RhdGEoRUxFTVMpOwoJZG91YmxlIHM7Cglkb3VibGUgZTsKCglzID0gYmFrYV9zZWNfY291bnQoKTsKCXF1aWNrc2VsZWN0KHAxLCBwMSArIEVMRU1TIC0gMSwgcDEgKyBUT1BTUyAtIDEpOwoJZSA9IGJha2Ffc2VjX2NvdW50KCk7CglmcHJpbnRmKHN0ZG91dCwgInR1cm5hcm91bmQgdGltZSA6Oj0gJS4wNGxmIHNlY1xuIiwgZSAtIHMpOwoKCXMgPSBiYWthX3NlY19jb3VudCgpOwoJcXVpY2tzZWxlY3QocDIsIHAyICsgRUxFTVMgLSAxLCBwMiArIFRPUFNTIC0gMSk7CgllID0gYmFrYV9zZWNfY291bnQoKTsKCWZwcmludGYoc3Rkb3V0LCAidHVybmFyb3VuZCB0aW1lIDo6PSAlLjA0bGYgc2VjXG4iLCBlIC0gcyk7CgoJZnJlZV9kYXRhKHAxKTsKCWZyZWVfZGF0YShwMik7CglyZXR1cm4gMDsKfQo=