#include <iostream>
#include <cstdlib>

#define N 10

//swaps the two values in the list
void swap(int list[], int left, int right)
{
	/*
	temp variable for swap, doesn't have to be initialized, but is good practice
	*/
	int temp = 0;

	//swap with aid of temp
	temp = list[left];
	list[left] = list[right];
	list[right] = temp;
}

//partition divides and conquer
int partition(int list[], int low, int high)
{
	//left and right values in the array
	int left = 0, right = 0;
	int pivot_item = 0;
	int pivot = left = low;
	pivot_item = list[low];
	right = high;
	while (left < right)
	{
		// Move left while item < pivot 
		while (list[left] <= pivot_item)
		{
			left++;
		}
		// Move right while item > pivot 
		while (list[right] > pivot_item)
		{
			right--;
		}
	
		if (left < right)
			swap(list, left, right);
	}
	// right is final position for the pivot 
	list[low] = list[right];
	list[right] = pivot_item;
	return right;
}//end partition


void quickSort(int list[], int low, int high)
{
	int part = 0;

	if (low < high)
	{
		// divide and conquer
		part = partition(list, low, high);
		quickSort(list, low, part - 1);
		quickSort(list, part + 1, high);
	}
}

//we use function overloading here!
void quickSort(int list[])
{
	quickSort(list, 0, N - 1);
}


int main(void)
{
	int B[N] = { 9, 5, 7, 1, 3, 2, 0, 4, 8, 6 };

	int i = 0;

	//print unsorted array
	std::cout << "************** Result **************" << std::endl;
	std::cout << "The input array is:  " << std::endl;

	for (i = 0; i < N; i++)
	{
		std::cout << B[i] << " ";
	}
	std::cout << std::endl;

	// call quick sort
	quickSort(B);

	/* print the sorted array */
	std::cout << "The sorted array is: " << std::endl;

	for (i = 0; i < N; i++)
	{
		std::cout << B[i] << " ";
	}
	std::cout << std::endl;

	return 0;
}