#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;
}