#include <iostream>
#include <vector>
#include <time.h>
#define ARRAY_SIZE 10000000
using namespace std;
void randomize(vector<int> &arr);
bool isSorted(vector<int> &arr);
void quickSort(vector<int> &arr, int low, int high);
int partition(vector<int> &arr, int low, int high);
void quickSort2(vector<int> &arr, int low, int high);
int partition2(vector<int> &arr, int low, int high);
int main(void) {
clock_t timeStart, timeEnd;
vector<int> array(ARRAY_SIZE);
// quick sort1
randomize(array);
timeStart = clock();
quickSort(array, 0, ARRAY_SIZE-1);
timeEnd = clock();
if(!isSorted(array)) printf("not sorted.\n");
printf( "%s: %f sec\n", "quick1", (double)(timeEnd - timeStart) / CLOCKS_PER_SEC );
// quick sort2
randomize(array);
timeStart = clock();
quickSort2(array, 0, ARRAY_SIZE-1);
timeEnd = clock();
if(!isSorted(array)) printf("not sorted.\n");
printf( "%s: %f sec\n", "quick2", (double)(timeEnd - timeStart) / CLOCKS_PER_SEC );
return 0;
}
void randomize(vector<int> &arr) {
srand((unsigned) time(NULL));
for(int i = 0; i < ARRAY_SIZE; ++i) {
arr[i] = rand();
}
}
bool isSorted(vector<int> &arr) {
for(int i = 1; i < ARRAY_SIZE; ++i) {
if(arr[i-1] > arr[i]) return false;
}
return true;
}
void quickSort(vector<int> &arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int partition(vector<int> &arr, int low, int high) {
int pivot = arr[high];
int i = low;
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
swap(arr[i], arr[j]);
i++;
}
}
swap(arr[i], arr[high]);
return i;
}
/*
// GeeksforGeeksのものは以下なのですが、これだとさらに遅くなります
int partition(vector<int> &arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) { // この = のせいらしい
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
*/
void quickSort2(vector<int> &arr, int low, int high) {
if (low < high) {
int pi = partition2(arr, low, high);
quickSort2(arr, low, pi - 1);
quickSort2(arr, pi + 1, high);
}
}
int partition2(vector<int> &arr, int low, int high) {
int pivot = arr[high];
int i = low;
int j = high-1;
for ( ; ; ) {
while (arr[i] < pivot) i++;
while (i < j && pivot < arr[j]) j--;
if (i >= j) break;
swap(arr[i], arr[j]);
i++;
j--;
}
swap(arr[i], arr[high]);
return i;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8dGltZS5oPgoKI2RlZmluZSBBUlJBWV9TSVpFIDEwMDAwMDAwCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdm9pZCByYW5kb21pemUodmVjdG9yPGludD4gJmFycik7CmJvb2wgaXNTb3J0ZWQodmVjdG9yPGludD4gJmFycik7Cgp2b2lkIHF1aWNrU29ydCh2ZWN0b3I8aW50PiAmYXJyLCBpbnQgbG93LCBpbnQgaGlnaCk7CmludCBwYXJ0aXRpb24odmVjdG9yPGludD4gJmFyciwgaW50IGxvdywgaW50IGhpZ2gpOwp2b2lkIHF1aWNrU29ydDIodmVjdG9yPGludD4gJmFyciwgaW50IGxvdywgaW50IGhpZ2gpOwppbnQgcGFydGl0aW9uMih2ZWN0b3I8aW50PiAmYXJyLCBpbnQgbG93LCBpbnQgaGlnaCk7CgppbnQgbWFpbih2b2lkKSB7CiAgICBjbG9ja190IHRpbWVTdGFydCwgdGltZUVuZDsKICAgIAogICAgdmVjdG9yPGludD4gYXJyYXkoQVJSQVlfU0laRSk7CiAgICAKICAgIC8vIHF1aWNrIHNvcnQxCiAgICByYW5kb21pemUoYXJyYXkpOwogICAgdGltZVN0YXJ0ID0gY2xvY2soKTsKICAgIHF1aWNrU29ydChhcnJheSwgMCwgQVJSQVlfU0laRS0xKTsKICAgIHRpbWVFbmQgPSBjbG9jaygpOwogICAgaWYoIWlzU29ydGVkKGFycmF5KSkgcHJpbnRmKCJub3Qgc29ydGVkLlxuIik7CiAgICBwcmludGYoICIlczogJWYgc2VjXG4iLCAicXVpY2sxIiwgKGRvdWJsZSkodGltZUVuZCAtIHRpbWVTdGFydCkgLyBDTE9DS1NfUEVSX1NFQyApOwogICAgCiAgICAvLyBxdWljayBzb3J0MgogICAgcmFuZG9taXplKGFycmF5KTsKICAgIHRpbWVTdGFydCA9IGNsb2NrKCk7CiAgICBxdWlja1NvcnQyKGFycmF5LCAwLCBBUlJBWV9TSVpFLTEpOwogICAgdGltZUVuZCA9IGNsb2NrKCk7CiAgICBpZighaXNTb3J0ZWQoYXJyYXkpKSBwcmludGYoIm5vdCBzb3J0ZWQuXG4iKTsKICAgIHByaW50ZiggIiVzOiAlZiBzZWNcbiIsICJxdWljazIiLCAoZG91YmxlKSh0aW1lRW5kIC0gdGltZVN0YXJ0KSAvIENMT0NLU19QRVJfU0VDICk7CiAgICAKICAgIHJldHVybiAwOwp9Cgp2b2lkIHJhbmRvbWl6ZSh2ZWN0b3I8aW50PiAmYXJyKSB7CiAgICBzcmFuZCgodW5zaWduZWQpIHRpbWUoTlVMTCkpOwogICAgCiAgICBmb3IoaW50IGkgPSAwOyBpIDwgQVJSQVlfU0laRTsgKytpKSB7CiAgICAgICAgYXJyW2ldID0gcmFuZCgpOwogICAgfQp9Cgpib29sIGlzU29ydGVkKHZlY3RvcjxpbnQ+ICZhcnIpIHsKICAgIGZvcihpbnQgaSA9IDE7IGkgPCBBUlJBWV9TSVpFOyArK2kpIHsKICAgICAgICBpZihhcnJbaS0xXSA+IGFycltpXSkgcmV0dXJuIGZhbHNlOwogICAgfQogICAgcmV0dXJuIHRydWU7Cn0KCnZvaWQgcXVpY2tTb3J0KHZlY3RvcjxpbnQ+ICZhcnIsIGludCBsb3csIGludCBoaWdoKSB7CiAgICBpZiAobG93IDwgaGlnaCkgeyAKICAgICAgICBpbnQgcGkgPSBwYXJ0aXRpb24oYXJyLCBsb3csIGhpZ2gpOyAKICAKICAgICAgICBxdWlja1NvcnQoYXJyLCBsb3csIHBpIC0gMSk7CiAgICAgICAgcXVpY2tTb3J0KGFyciwgcGkgKyAxLCBoaWdoKTsKICAgIH0KfQoKaW50IHBhcnRpdGlvbih2ZWN0b3I8aW50PiAmYXJyLCBpbnQgbG93LCBpbnQgaGlnaCkgewogICAgaW50IHBpdm90ID0gYXJyW2hpZ2hdOwogICAgCiAgICBpbnQgaSA9IGxvdzsKICAKICAgIGZvciAoaW50IGogPSBsb3c7IGogPD0gaGlnaCAtIDE7IGorKykgewogICAgICAgIGlmIChhcnJbal0gPCBwaXZvdCkgewogICAgICAgICAgICBzd2FwKGFycltpXSwgYXJyW2pdKTsKICAgICAgICAgICAgaSsrOwogICAgICAgIH0gCiAgICB9CiAgICBzd2FwKGFycltpXSwgYXJyW2hpZ2hdKTsKICAgIHJldHVybiBpOwp9Ci8qCi8vIEdlZWtzZm9yR2Vla3Pjga7jgoLjga7jga/ku6XkuIvjgarjga7jgafjgZnjgYzjgIHjgZPjgozjgaDjgajjgZXjgonjgavpgYXjgY/jgarjgorjgb7jgZkKaW50IHBhcnRpdGlvbih2ZWN0b3I8aW50PiAmYXJyLCBpbnQgbG93LCBpbnQgaGlnaCkgewogICAgaW50IHBpdm90ID0gYXJyW2hpZ2hdOwogICAgCiAgICBpbnQgaSA9IGxvdyAtIDE7CiAgICAKICAgIGZvciAoaW50IGogPSBsb3c7IGogPD0gaGlnaCAtIDE7IGorKykgewogICAgICAgIGlmIChhcnJbal0gPD0gcGl2b3QpIHsgLy8g44GT44GuID0g44Gu44Gb44GE44KJ44GX44GECiAgICAgICAgICAgIGkrKzsKICAgICAgICAgICAgc3dhcChhcnJbaV0sIGFycltqXSk7CiAgICAgICAgfQogICAgfQogICAgc3dhcChhcnJbaSArIDFdLCBhcnJbaGlnaF0pOwogICAgcmV0dXJuIGkgKyAxOyAKfQoqLwoKCnZvaWQgcXVpY2tTb3J0Mih2ZWN0b3I8aW50PiAmYXJyLCBpbnQgbG93LCBpbnQgaGlnaCkgewogICAgaWYgKGxvdyA8IGhpZ2gpIHsKICAgICAgICBpbnQgcGkgPSBwYXJ0aXRpb24yKGFyciwgbG93LCBoaWdoKTsKCiAgICAgICAgcXVpY2tTb3J0MihhcnIsIGxvdywgcGkgLSAxKTsKICAgICAgICBxdWlja1NvcnQyKGFyciwgcGkgKyAxLCBoaWdoKTsKICAgIH0gCn0gCgppbnQgcGFydGl0aW9uMih2ZWN0b3I8aW50PiAmYXJyLCBpbnQgbG93LCBpbnQgaGlnaCkgewogICAgaW50IHBpdm90ID0gYXJyW2hpZ2hdOwogICAgaW50IGkgPSBsb3c7CiAgICBpbnQgaiA9IGhpZ2gtMTsKICAgIAogICAgZm9yICggOyA7ICkgewogICAgICAgIHdoaWxlIChhcnJbaV0gPCBwaXZvdCkgaSsrOwogICAgICAgIHdoaWxlIChpIDwgaiAmJiBwaXZvdCA8IGFycltqXSkgai0tOwogICAgICAgIGlmIChpID49IGopIGJyZWFrOwogICAgICAgIHN3YXAoYXJyW2ldLCBhcnJbal0pOwogICAgICAgIGkrKzsgCiAgICAgICAgai0tOwogICAgfQogICAgc3dhcChhcnJbaV0sIGFycltoaWdoXSk7CiAgICByZXR1cm4gaTsKfSAKICAKICAK