//
//  main.c
//  Sorting
//

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

int selectRandomPosition(int* target, int left, int right){
    srand((unsigned) time(NULL));
    int length = right - left + 1;
    int r = left + rand()%length;
    return r;
}

int selectMaxPosition(int* target, int left, int right){
    int m = target[left];
    int r = left;
    for(int i=left+1; i<= right; i++){
        if( m < target[i]){
            m = target[i];
            r = i;
        }
    }
    return r;
}

int partition(int* target, int left, int right) {
    // Select a number between left and right at random.
    int random = selectRandomPosition(target, left, right);
    // To select the maximum element, use:
    // int random = selectMaxPosition(target, left, right);
    // Exchange target[right] and target[random].
    int tmp = target[right];
    target[right] = target[random];
    target[random] = tmp;
    
    int pivot = target[right];
    int i = left-1;  // i scans the array from the left.
    int j = right;  // j scans the array from the right.
    for (;;) {
        // Move from the left until hitting a value no less than the pivot.
        for(i++; target[i] < pivot; i++){}
        // Move from the right until hitting a value no greater than the pivot.
        for(j--; pivot < target[j] && i < j; j--){}
        if (i >= j)  break;
        // Exchange target[i] and target[j].
        tmp = target[i];  target[i] = target[j];  target[j] = tmp;
    }
    // Exchange target[i] and target[right].
    tmp = target[i];  target[i] = target[right];  target[right] = tmp;
    return i;
}


void randomQuickSort1(int* target, int left, int right ) {
    if (left < right){
        int i = partition(target,left,right);
        // i indicates the position of the pivot.
        randomQuickSort1(target, left, i - 1);
        randomQuickSort1(target, i + 1, right);
    }
}

int main(int argc, char** argv){

/*
    // Generate the running example array of size 12
    int n = 12;
    int target[12] = {48, 195, 12, 49, 198, 24, 99, 140, 48, 195, 12, 48};
*/
    
    // Generate an array of random numbers
    int n = 10000000; // array length
    int* target;
    target = (int *)malloc( sizeof(int) * n);  // Use the heap to generate a long array
    for(int i=0; i<n; i++) {
        target[i] = rand()%256;
    }

    clock_t sTime, eTime;
    sTime = clock();
    
    randomQuickSort1(target, 0, n-1);
    
    eTime = clock();
    printf("Elapsed time = %f sec.\n", (float)(eTime - sTime)/(float)CLOCKS_PER_SEC);
    
    // Check if the target is sorted
    int sorted = 1;
    for(int i = 0; i < (n-1); i++){
        if( target[i] > target[i+1]) sorted = 0;
    }
    if (sorted == 1) printf("sorted\n");
    
    free(target);
    
    return 0;  // 0 means EXIT_SUCCESS
}