#include <iostream>
#include <algorithm>
#include <ctime>
#include <fstream>
#include <cstdlib>
 
using namespace std;
//functions used for sorts
void generateSortedArray(int arraySize, int*& sortedArray);
void generateReversedArray(int arraySize, int*& reversedArray);
void generateRandomArray(int arraySize, int*& randomArray);
int insertionSort(int arraySize, int array[]); 
void sort(int arraySize, int*& sortedArray, int*& reversedArray, int*& randomArray, int algoChoice, int sortChoice);
void quickSort(int *array, int left, int right);
int partition(int *array, int left, int right);
void printArray(int arraySize, int *array);
int main()
{
 //declaration of variables to be used throughout program
 char answer;
 int arraySize = 0,algoChoice = 0, sortChoice = 0;
 //initialization of pointer arrays
 int *sortedArray = NULL;
 int *reversedArray = NULL;
 int *randomArray = NULL;
 randomArray = new int [arraySize];
 sortedArray=new int[arraySize];
 reversedArray=new int[arraySize];
 
 
 cout << "Enter the number of elements in the array: "; 
 cin >> arraySize;
 cout << endl;
 
 //used 6500 since 6400 is the highest my computer will calculate
 while(arraySize >= 0 && arraySize <=6500)
 {
  cout << "What algorithm would you like to use (1 = insertion 2 = quicksort): ";
  cin >> algoChoice;
  cout << endl;
 
 
  //breaks into the switches
  sort(arraySize, sortedArray, reversedArray, randomArray, algoChoice, sortChoice);
 
 
 
  cin >> answer;
  //if the user wants to calculate another sort, they just enter y
  if(answer =='y')
  {
   cout << "Enter the number of elements in the array : ";
   cin >> arraySize;
   cout << endl;
  }
  else
   return -1;
 }
 //deallocation of memory
 delete [] randomArray;
 delete [] reversedArray;
 delete [] sortedArray;
return 0;
}
void generateSortedArray(int arraySize, int*& sortedArray)
{
 //sets range for elements
 for(int i=0; i<arraySize; i++)
  {
 
   sortedArray[i] = (rand() % arraySize)+1;
 
  }
 
 //sorts in ascending order 
 int temp;
 int counter, index;
 for (counter = 0; counter < arraySize - 1; counter++)
 {
  for (index = 0; index < arraySize - 1 - counter; index++)
   if (sortedArray[index] > sortedArray[index+1])
   {
    temp = sortedArray[index];
    sortedArray[index] = sortedArray[index+1];
    sortedArray[index+1] = temp;
   }
 }
 
 
}
void generateReversedArray(int arraySize, int*& reversedArray)
{
 for(int i=0; i<arraySize; i++)
  {
 
   reversedArray[i] = (rand() % arraySize)+1;
 
  }
 //code to reverse the elements
 int temp;
 int counter, index, flag = 1;
 for (counter = 1; (counter <= arraySize) && flag; counter++)
 {
  flag = 0;
  for (index = 0; index < (arraySize - 1); index++)
   if (reversedArray[index+1] > reversedArray[index])
   {
    temp = reversedArray[index];
    reversedArray[index] = reversedArray[index+1];
    reversedArray[index+1] = temp;
    flag =1;
   }
 }
 
}
void generateRandomArray(int arraySize, int*& randomArray)
{
 for(int i=0; i<arraySize; i++)
  {
 
   randomArray[i] = (rand() % arraySize)+1;
 
  }
 //shuffles elements in array
 random_shuffle(randomArray , (randomArray + arraySize));
 
}
 
//The insertion sort splits an array into two sub-arrays. 
//The first sub-array is always sorted and gets larger as the sort continues. 
//The second sub-array is unsorted and contains all the elements not yet inserted into the first sub-array.
// The second sub-array gets smaller as the sort progresses
int insertionSort(int arraySize, int *array) 
{
 int i,j,key;
 for(j=1; j<arraySize; j++)
 {
  key=array[j];
  i=j-1;
  while(array[i]>key && i>=0)
  {
   array[i+1]=array[i];
   i--;
  }
  array[i+1]=key;
 }
 return 0;
}
//This sort starts by dividing the original array into two sections (partitions) based upon the value of the first item in the array.
//the first section will contain all the elements with values less than the first item.  
//The second section will contain elements with values greater than (or equal to) the first element
void quickSort(int *array, int left, int right) 
{
 int middle;
 if(left<right)
 {
  middle=partition(array, left, right);
  quickSort(array,left,middle-1);
  quickSort(array,middle+1,right);
 }
 
 
} //end quicksort(...)
int partition(int *array, int left, int right)
{
 //the variable "middle" is the pivot of the process
 int middle = array[left];
 int i = left;
 int j = right+1;
 do
 {
  do
  {
   ++i; //increment i while the array element is less than the pivot and decrement j while it's greater.
  }while(array[i]<middle);
  do --j; while(array[j]>middle);
  if(i<j)//if i is less than j swap the elements
   swap(array[i], array[j]);
 }
 while(i<j);
 swap(array[j], array[left]);
 return j;//returns middle index
}
//main code 
void sort(int arraySize, int*& sortedArray, int*& reversedArray, int*& randomArray, int algoChoice, int sortChoice)
{
 //the clock variables, start and end, are used to time the execution for every sort
 clock_t start, end;
 
 
 //algorithm choice = insertion sort
 if (algoChoice == 1)
 {
 
  cout << "What sorting would you like to use: (1=sorted, 2=reversed, 3=random): ";
  cin >> sortChoice;
 
  switch(sortChoice)
  {
  //ascending array
  case 1:
 
   generateSortedArray(arraySize, sortedArray);
   start = clock();
   insertionSort(arraySize, sortedArray);
   end = clock();
   cout << endl;
   cout << "Duration: " << (double)(end-start)/CLOCKS_PER_SEC << endl;
   cout << "Writing contents of sorted array to sorted2^15.out" << endl;
   printArray(arraySize, sortedArray);
   break;
  case 2:
   //user selects 2: elements in descending order
   generateReversedArray(arraySize, reversedArray);
   start = clock();
   insertionSort(arraySize, reversedArray);
   end = clock();
   cout << endl;
   cout << "Duration: " << (double)(end-start)/CLOCKS_PER_SEC << endl;
   cout << "Writing contents of sorted array to sorted2^15.out" << endl;
   printArray(arraySize, reversedArray);
   break;
  case 3:
   //user selects 3: elements are randomized
   generateRandomArray(arraySize, randomArray);
   start = clock();
   insertionSort(arraySize, randomArray);
   end = clock();
   cout << endl;
   cout << "Duration: " << (double)(end-start)/CLOCKS_PER_SEC << endl;
   cout << "Writing contents of sorted array to sorted2^15.out" << endl;
   printArray(arraySize, randomArray);
   break;
  default:
   //user selects anything other than 1-3, this error prints
   cout << "Invalid choice of sort" << endl;
   break;
  }
  cout << endl;
  cout << "Do you want to test again? ";
  //end switch(sortChoice)
 }  //end if (algoChoice == 1)
 
 //choice 2 = quicksort
 else if (algoChoice == 2)
 {
  cout << "What sorting would you like to use: (1=sorted, 2=reversed, 3=random): ";
  cin >> sortChoice;
  switch(sortChoice)
  {
  //the left cell chosen will obviously be 0 since it's the first element of the array. the right
  //element is the array size minus 1 since arrays start at 0.
  case 1:
   generateSortedArray(arraySize, sortedArray);
   partition(sortedArray, 0, arraySize-1);
   start = clock();
   quickSort(sortedArray, 0, arraySize-1);
   end = clock();
   cout << endl;
   cout << "Duration: " << (double)(end-start)/CLOCKS_PER_SEC << endl;
   cout << "Writing contents of sorted array to sorted2^15.out" << endl;
   printArray(arraySize, sortedArray);
   break;
  case 2:
   generateReversedArray(arraySize, reversedArray);
   partition(reversedArray, 0, arraySize-1);
   start = clock();
   quickSort(reversedArray, 0, arraySize-1);
   end = clock();
   cout << endl;
   cout << "Duration: " << (double)(end-start)/CLOCKS_PER_SEC << endl;
   cout << "Writing contents of sorted array to sorted2^15.out" << endl;
   printArray(arraySize, reversedArray);
   break;
  case 3:
   generateRandomArray(arraySize, randomArray);
   partition(randomArray, 0, arraySize-1);
   start = clock();
   quickSort(randomArray, 0, arraySize-1);
   end = clock();
   cout << endl;
   cout << "Duration: " << (double)(end-start)/CLOCKS_PER_SEC << endl;
   cout << "Writing contents of sorted array to sorted2^15.out" << endl;
   printArray(arraySize, randomArray);
   break;
  default:
   cout << "Invalid choice of sort" << endl;
   break;
  }
  cout << endl;
  cout << "Do you want to test again? ";
  //end switch(sortChoice)
 } //end else if(algoChoice == 2)
 else
  cout << "Invalid algorithm choice" << endl;
}
//had trouble sending out to file. it would only send within 100-200 elements.
//couldn't find out why
void printArray(int arraySize, int *array)
{
 ofstream outFile;
 outFile.open("C:/Documents and Settings/user/My Documents/sorted2^15.out");
 
 
 for(int i=0; i< arraySize; i++)
 {
 
  outFile << array[i] << " ";
  if (i%8==0)
   outFile << endl;
 
 
 }
 
}

for(int i=0; i<arraySize; i++)
{
array[i] = (rand()%arraySize)+1;
}

 ofstream outFile;
 outFile.open("C:/Documents and Settings/user/My Documents/sorted2^15.out");
 
 
 for(int i=0; i< arraySize; i++)
 {
 
  outFile << array[i] << " ";
  if (i%8==0)
   outFile << endl;
 
}

    randomArray = new int [arraySize];
    sortedArray=new int[arraySize];
    reversedArray=new int[arraySize];
    cout << "Enter the number of elements in the array: "; 
    cin >> arraySize;

    cout << "Enter the number of elements in the array: ";     
    cin >> arraySize;
    randomArray = new int [arraySize];
    sortedArray=new int[arraySize];
    reversedArray=new int[arraySize];