// cmpt225sort_lab.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include <cstdlib>
#include "time.h"
using std::cout;
using std::endl;
using std::rand;
using std::srand;

int qs(int arr[], int n);
int quicksort(int arr[], int low, int high);
int partition(int arr[], int low, int end, int & count);
void swap(int arr[], int i, int j);
int* getRandomArray(int n);
int* getReversedArray(int n);


int main()
{
	srand(time(NULL));
	// TO DO - print number of comparisons to sort:
	// RANDOM: 10,100,1000,1000000
	// REVERSED: 10,100,1000

	cout << endl;
	return 0;
}

// Sorts an array using quicksort and returns the number of comparisons
// PARAM: arr is the array
//        n is the size of the array
int qs(int arr[], int n)
{
	return quicksort(arr, 0, n - 1);
}

// Sorts a subarray and returns the number of comparisons
// PARAM: arr is the array
//        low and end are the subarray indexes
// PRE: 0 < low, end < array length
//        i and j are indexes whose values are swapped
int quicksort(int arr[], int low, int high)
{
	int count = 0;
	if (low < high) {
		int pivot = partition(arr, low, high, count);
		count += quicksort(arr, low, pivot - 1);
		count += quicksort(arr, pivot + 1, high);
	}
	// implicit base case (do nothing)
	return count;
}

// Partitions a subarray about the pivot, where the pivot
// is the last element of the array
// PRE: 0 < low, end < array length
// PARAM: arr - the array
//        low and end are the subarray indexes
//        count records the number of comparisons made
int partition(int arr[], int low, int end, int & count)
{
	int pivot = arr[end]; // set pivot value
	int high = end - 1;

	// Process array until low and high meet
	while (low < high) {
		count++; // comparisons
		// Find elements that are on the wrong side
		if (arr[low] <= pivot) {
			low++;
		}
		else if (arr[high] >= pivot) {
			high--;
		}
		else {
			swap(arr, low, high);
			low++;
			high--;
		}
	}
	// Put the pivot in the correct place
	if (arr[low] < pivot) {
		swap(arr, low + 1, end);
		return low + 1;
	}
	else {
		swap(arr, low, end);
		return low;
	}
}

// Swaps two element of an array
// PARAM: arr is the array
//        i and j are indexes whose values are swapped       
// PRE: 0 < low, end < array length
void swap(int arr[], int i, int j)
{
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

// Creates a random array of integers, of the given size
int* getRandomArray(int n) {
	int* result = new int[n]; //C++ dynamic array
								// Insert random ints in result
	for (int i = 0; i < n; i++) {
		result[i] = rand();
	}
	return result;
}

// Creates a reversed array of integers, of the given size
int* getReversedArray(int n)
{
	int* arr = new int[n];
	for (int i = 0; i < n; i++) {
		arr[i] = n - i;
	}
	return arr;
}