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

#define SORT_ARRAY_SIZE       10000
#define PIVOT_FIRST           1
#define PIVOT_LAST            0
#define PIVOT_MEDIAN_OF_THREE 0

void QuickSort(int *array, int start, int end);
int ChoosePivot(int *array, int start, int end);

static long long compNum = 0;

int main() {
    // load txt into array buffer
    int *array = (int*)malloc(sizeof(int)*SORT_ARRAY_SIZE+10);
    FILE *pFile;
    pFile = fopen("QuickSort.txt", "r");
    if (pFile == NULL)
        perror("Error openin file.\n");
    rewind(pFile);
    for (int i = 0; i < SORT_ARRAY_SIZE; i++) {
        fscanf(pFile, "%d", &array[i]);
    }
    fclose(pFile);

    // quick sort array
    QuickSort(array, 0, SORT_ARRAY_SIZE-1);
    printf("number of comparisons is %lld\n", compNum);

    free(array);
    return 0;
}

void QuickSort(int *array, int start, int end) {
    if (start >= end) return;
    else if ((end - start == 1)&&(array[start]>array[end])) {
        compNum += 1;
        int temp = array[start];
        array[start] = array[end];
        array[end] = temp;
    }
    else {
        compNum += (end - start);
        // choose the pivot and do proper swap
        int pivot = ChoosePivot(array, start, end);

        // i denotes the location of pivot
        int i = start + 1;
        // j for loop the unpartitioned part
        for (int j = start + 1; j < end + 1; j++) {
            if (array[j] < pivot) {
                int temp = array[j];
                array[j] = array[i];
                array[i] = temp;
                i++;
            }
        }
        // swap the pivot and array[i-1]
        int temp = array[i-1];
        array[i-1] = pivot;
        array[start] = temp;

        // quick sort the left and right partition
        QuickSort(array, start, i-2);
        QuickSort(array, i, end);
    }
}

int ChoosePivot(int *array, int start, int end) {
    int pivot = -1;
#if PIVOT_FIRST
    // choose the first element as pivot
    pivot = array[start];
    return pivot;
#elif PIVOT_LAST
    // choose the last element as pivot
    // swap the first and the last element
    pivot = array[end];
    array[end] = array[start];
    array[start] = pivot;
    return pivot;
#elif PIVOT_MEDIAN_OF_THREE
    // choose the median of first, mid and last
    // element as pivot
    int mid = (start + end) / 2;
    int max = (array[start] > array[end]) ? (array[start]) : (array[end]);
    max = (max > array[mid]) ? max : array[mid]; 
    int min = (array[start] < array[end]) ? (array[start]) : (array[end]);
    min = (min < array[mid]) ? min : array[mid];
    if (array[start] != max && array[start] != min) {
        pivot = array[start];
        return pivot;
    }
    if (array[mid] != max && array[mid] != min) {
        pivot = array[mid];
        array[mid] = array[start];
        array[start] = pivot;
        return pivot;
    }
    if (array[end] != max && array[end] != min) {
        pivot = array[end];
        array[end] = array[start];
        array[start] = pivot;
        return pivot;
    }
#endif
}