#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
}</pre>