/*	Program 2
	Author: B. Josh Becker
*/
 
#include <iostream>				// preprocessor
#include <ctime>
#include <cstdlib>
#include <cstdio>
 
using namespace std;
 
void mergesort(int[], int, int);
void merge(int[], int, int);
void quicksort(int[], int, int);
void choosePivot(int[], int, int);
void partition(int[], int, int, int&);
void insertionSort(int[], int);
 
void main(){
 
	int numbers[200] = {0};
	int response, choice,threshhold;
 
	cout << endl << "Would you like to randomly choose a list or should I create one at random?" << endl;
	cout << "\t1) Create one (less than 100 values)" << endl;
	cout << "\t2) Random" << endl;
	cin >> choice;
 
	switch(choice){
	case 1:
		{	
			int number;
			cout << endl << "Please enter the number of values you would like in the array (less than 100):";
			cin >> number;
			cout << endl << "Please enter each number followed by the return key" << endl;
			if (number>100)
				break;
			for (int i=0;i<number;i++)
				cin >> numbers[i];
			cout << "Here are the numbers you just entered:" << endl;
			for(i=0;i<number;i++)
				cout << numbers[i] << " ";
			break;
		}
	case 2:
		{		
			int number;
			cout << endl << "Please enter the number of values you would like in the array:";
			cin >> number;
			srand( (unsigned)time( NULL ) );
			for(int i=0;i<number;i++)
				numbers[i]=rand();
 
			cout << "Here are the random values:" << endl;
 
			for(i=0;i<number;i++)
				cout << numbers[i] << " ";
			break;
		}
	default:{
		cout << "Sorry invalid value" << endl;
		break;
			}
 
	}
 
	cout << endl << "Please enter a threshold value:" << endl;
	cin >> threshhold;
 
	cout << "This program allows the user to sort numbers with different sorting methods" << endl;
	cout << "Would you like to use :" << endl;
	cout << "\t1) Quicksort" << endl;
	cout << "\t2) Mergesort" << endl;
	cout << "\t3) Insertionsort" << endl;
	cin >> response;
 
}
 
// Start for Mergesort
 
void mergesort(int a[], int left, int right)
{
	if(left<right) 
	{
		int mid=(left + right)/2;
		mergesort(a, left, mid);
		mergesort(a, mid+1, right);
		merge(a,left,right);
	}
}
 
 
void merge(int a[],int left, int right)
{
	int 	size=right-left+1,
		mid=(left+right)/2;
	int y, put;
	int *b=new int[size];
	int count=0;
	for(int x=left;x<=mid;x++,count++)
	{
		b[count]=a[x];
	}
	for(x=right;x>=mid+1;x--,count++)
	{
		b[count]=a[x];
	}
	for(x=0,y=size-1,put=left;x<=y;put++)	
	{
		if(b[x]<=b[y])
		{
			a[put]=b[x];
			x++;
		}
		else
		{
			a[put]=b[y];
			y--;
		}
	}
	delete[] b;
}
 
// Start for quicksort
 
void choosePivot(int theArray[], int first, int last){
{ 
	int  pivotIndex;
	int mid = (first + last) / 2;
 
    if( theArray[ first ] <= theArray[ mid ] )
    {    if( theArray[ mid ] <= theArray[ last ] )  pivotIndex = mid;
          else  pivotIndex = ( theArray[ first ] <= theArray[ last ] ? last : first );
    }
    else if( theArray[ last ] <= theArray[ mid ] )  pivotIndex = mid;
    else  pivotIndex = ( theArray[ first ] <= theArray[ last ] ? first : last );
      swap( theArray[ first ],  theArray[ pivotIndex ] );
}
}
 
void partition(int theArray[], int first, int last, int& pivotIndex)
{
		choosePivot(theArray, first, last);
		int pivot = theArray[first];
 
		int lastS1 = first;
		int firstUnknown = first + 1;
 
		for (; firstUnknown<=last;++firstUnknown)
		{
			if (theArray[firstUnknown]<pivot)
			{
				++lastS1;
				swap(theArray[firstUnknown],theArray[lastS1]);
			}
		}
		swap(theArray[first], theArray[lastS1]);
		pivotIndex = lastS1;
}
 
void quicksort(int theArray[], int first, int last)
{
	int pivotIndex;
 
	if (first<last)
	{
		partition(theArray, first, last, pivotIndex);
 
		quicksort(theArray, first, pivotIndex-1);
		quicksort(theArray, pivotIndex+1, last);
	}
}
 
 
//Start insertion sort
 
void insertionSort(int theArray[], int n)
{
	for (int unsorted=1;unsorted<n;++unsorted)
	{
		int nextItem = theArray[unsorted];
		int loc = unsorted;
 
		for (;(loc>0) && (theArray[loc-1]>nextItem);--loc)
			theArray[loc] = theArray[loc-1];
 
		theArray[loc] = nextItem;
	}
}