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

	// Function Prototypes
	void quickSortWrapper(int *arr, int len);
	void quickSort(int *arr, int left, int right);
	int partition(int *arr, int left, int right);
	void swap(int *arr, int a, int b);
	void printArr(int *arr, int len);

	// Calls recursive quickSort with appropriate arguments
	void quickSortWrapper(int *arr, int len) { quickSort(arr, 0, len - 1); }

	// Recursively finds partition and calls quickSort() on
	// sub-array formed on either side of the partition
	// Base case when sub-array has a size of 1 (left >= right)
	void quickSort(int *arr, int left, int right) {
		if (left >= right)
			return;
		int k = partition(arr, left, right); // O(n)
		quickSort(arr, left, k - 1);         // T(n/2)
		quickSort(arr, k + 1, right);        // T(n/2)

		// Recurrence Relation: O(n) + T(n/2) + T(n/2) = 2T(n/2) + O(n)
		// Average Runtime - O(nlogn)
		// When poor pivot is chosen; often when array is sorted and leftmost
		// or rightmost index chosen as pivot or if largest or smallest element
		// is otherwise chosen as the pivot every iteration causing each sub-array
		// to contain n-1 elements; the result will be an O(n^2) runtime.
	}

	// Selects a random pivot
	// Swaps pivot with leftmost index
	// Arranges array such that left side ends up with values <= pivot
	// and right side ends up with values >= pivot
	// Swaps pivot value to final - fixed - index and returns the index
	int partition(int *arr, int left, int right) {
		int pivot = rand() % (right - left + 1) + left;
		swap(arr, left, pivot);

		int L = left + 1;
		int R = right;
		while (L <= R) {
			while (L <= R && arr[L] <= arr[left]) {
				L++;
			}
			while (L <= R && arr[R] >= arr[left]) {
				R--;
			}
			if (L < R)
				swap(arr, L, R);
		}
		swap(arr, left, R);
		return R;
	}

	void swap(int *arr, int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}

	// Print integer array to screen
	void printArr(int *arr, int len) {
		for (int i = 0; i < len; i++)
			printf("%d ", arr[i]);
		printf("\n\n");
	}

	int main(void) {
		int len = 20;
		int *arr = malloc(len * sizeof(int));
		for (int i = 0; i < len; i++) {
			arr[i] = rand() % 100;
		}
		printf("Printing Array...\n\n");
		printArr(arr, len);
		printf("Applying Quick Sort...\n\n");
		quickSortWrapper(arr, len);
		printf("Printing Sorted Array...\n\n");
		printArr(arr, len);
		free(arr);
		return 0;
	}