#include <iostream>
#include "apvector.h"
#include <time.h>
#include <iomanip.h>
#include "apstring.h"

using namespace std; //introduces namespace std

const int MAXVAL = 5000;

void RandomFill(apvector <int> & NumberList, int Max);
double Sort(apvector <int> & SortVector, int sortchoice);
int MenuSelection();
void SelectSort(apvector <int> & A);
void InsertSort(apvector <int> & A);
void QuickSort(apvector <int> & A, int front, int back);
int Partition( apvector <int> & A, int front, int back);
void MergeSort(apvector <int> & A);
void Swap ( int & a, int & b);
void Display(int choice, double duration);


int main()
{
    char ch;
    int ListLength, choice;
    double  duration;    
    cout << "How many random numbers would you like to generate?\n";
    cin >> ListLength;
    apvector <int> NumberList(ListLength);
    RandomFill( NumberList, MAXVAL);
    do
    {
        apvector <int> sortVector = NumberList;
        
/*   */    cout << "Original vector unsorted:\n";
        for (int i = 0; i < sortVector.length(); i++)
           cout << setw(6) << sortVector[i];
        cout << endl;
/**/ 
        cout << "Choose your sort Method\n";
        choice = MenuSelection();
        
       
        
        duration = Sort(sortVector, choice);
        
/*  */                  cout << "Final vector sorted:\n";
        for (int i = 0; i < sortVector.length(); i++)
           cout << setw(6) << sortVector[i];
        cout << endl;
/**/   
        Display( choice, duration);
        cout << "Run again? (y/n)\n"; 
        cin >> ch;
    } while ( ch == 'y' || ch == 'Y' );
}

void RandomFill(apvector <int> & List, int Max)
{
  srand(time(0));
  for (int i=0; i < List.length(); i++)
    List[i]= rand()% Max+1;
}

int MenuSelection()
{  int menuNum;

   cout << "(1) Selection Sort\n";
   cout << "(2) Insertion Sort\n";
   cout << "(3) Quick Sort\n";
   cout << "(4) Merge Sort\n\n";
   cout << "Your choice: ";
   cin >> menuNum;
   return menuNum;
}

void SelectSort(apvector <int> & A)
{
     int i, j, min;
     for (i =0; i < A.length(); i++) 
     {
          min  = i;
          for (j = i+1; j< A.length(); j++)
            if (A[j] < A[min])
              min = j;
          Swap(A[min],A[i]);
     }
}

void InsertSort(apvector <int> & A)
{
  int f, i;
  int temp;

  for (f = 1; f < A.length(); f++) 
  {
      if (A[f] < A[f-1])
      {
	      temp = A[f];
	      i    = f-1;
	      while ((i>=0)&&(A[i]>temp)) 
	      {
	         A[i+1] = A[i];
	         i--;
	      }
	      A[i+1]=temp;
      }
  }
}


void QuickSort(apvector <int> & A, int front, int back)
{   
   int pivotPosition = Partition( A, front, back);
   if (pivotPosition -front > 0)
     QuickSort( A, front, pivotPosition -1);
   if (back - pivotPosition > 0)
   QuickSort( A, pivotPosition + 1, back);

}

int Partition( apvector <int> & A, int front, int back)
{ 

/*cout << "front = "<<front << " back = " << back <<endl;  */

    if (front>=back)
      return front;      
    int pivotIndex = front;
    int i = front+1;
    int j = back;
    do
    { 
/*    cout << "i = " << i << " j = " << j << endl;  */
	    while((A[pivotIndex] > A[i]) && (i<back) )
	       i++;
        while (A[pivotIndex] <= A[j] && j > front)
	       j--;
	    if ( i < j )
	    {
	       Swap ( A[i], A[j] );
/*	       cout << "with i = " << i << " and j="<<j<<" swapped A[i],A[j]\n";  */
	     }
    } while ( i < j );
/*    cout << "exitted while...i="<<i<<" j="<<j<<" pivinx="<<pivotIndex<<endl;  */
    Swap ( A[pivotIndex], A[j] );   
 /*   cout << "Swapped A[pivotIndex], A[j]\n";  */
    return j;
}


void MergeSort(apvector <int> & A)
{
  cout << "MergeSort running\n";

}

double Sort(apvector <int> & SortVector, int sortchoice)
{
    time_t start, stop;
    start=time(0);                       // start time to begin timing
    switch (sortchoice)
    {
      case 1 :
         SelectSort(SortVector);
         break;
       case 2:
         InsertSort(SortVector);
         break;
       case 3:
         QuickSort(SortVector, 0, SortVector.length()-1);
         break;
       case 4:
         MergeSort(SortVector);
         break;
       default:
         cout << "No sort selected\n";
    }
    
    stop=time(0);             // stop timing 
    return difftime(stop, start);
}

void Display(int choice, double duration)
{
   apstring SortName;

    switch (choice)
    {
      case 1 :
         SortName = "Selection Sort";;
         break;
       case 2:
         SortName = "Insertion Sort";
         break;
       case 3:
         SortName = "Quick Sort";
         break;
       case 4:
         SortName = "Merge Sort";
         break;
       default:
         cout << "No sort selected\n";
    }
    cout << "Using " << SortName << " required " << duration << " seconds.\n";
}


void Swap ( int & a, int & b)
{
   int c = a;
       a = b;
       b = c;
}