//generating random numbers
#include<iostream>
#include<fstream>
#include<ctime>
#include<ratio>
#include<chrono>
using namespace std;
//n for no. of elements
int n;
//1 sorter array and 1 real array
int arr[10000];
int arr_temp[10000];
//float merge_time;
//float insertion_time;
//float quicksortmidpiv_time;
void gen()
{
   srand(time(0));
   cout<<"Enter length of list : ";
   cin>>n;
   fstream file;
   file.open("RawData.txt", ios::out);
   if(!file)
   {
       cout<<"FIle not found";
   }
   else
   {
       for(int i=0;i<n;i++)
       {
           file<<rand()<<" ";
       }
   }
   file.close();
}
void duplicateFile()
{
   ifstream fin;
   fin.open("RawData.TXT");
//ofstream fout;
//fout.open("SortMerge.TXT");
    int ch;
    int k=0;
    int num=0;
    int count=0;
//int length=0;
//cout<<"Please enter length of file : ";
//cin>>length;
    while(count!=n)  //n ki jaga length
    {
        fin>>num;
        cout<<" "<<num;
        if(ch!=32)
        {
            arr[k]=num;
            k++;
        }
        count++;
        //fout<<ch;    //this copies the data
   }
    cout<<"\n\nData has been copied\n";
    for(int i=0;i<k;i++)
    {
       cout<<i+1<<" : "<<arr[i]<<"\n";
   }
    fin.close();
    for(int i=0;i<n;i++)
    {
        arr_temp[i]=arr[i];
   }
}

/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i - 1;

        /* Move elements of arr[0..i-1], that are
       greater than key, to one position ahead
       of their current position */
       while (j >= 0 && arr[j] > key)
       {
           arr[j + 1] = arr[j];
           j = j - 1;
       }
       arr[j + 1] = key;
   }
}

void InsertionSort()
{
   for(int i=0;i<n;i++)
   {
       arr[i]=arr_temp[i];
   }
   insertionSort(arr, n);
   cout<<"\n\n\nIsertion Sort begins.\n\n\n";
   ofstream fout;
   fout.open("SortInsertion.TXT");
   for(int i=0;i<n;i++)
   {
       fout<<arr[i]<<" ";
   }
   cout<<"Contents copied in SortInsertion.TXT";
   fout.close();
}

void merge(int array[], int const left, int const mid, int const right)
{
   auto const subArrayOne = mid - left + 1;
   auto const subArrayTwo = right - mid;
   // Create temp arrays
   auto *leftArray = new int[subArrayOne];
   auto     *rightArray = new int[subArrayTwo];
   // Copy data to temp arrays leftArray[] and rightArray[]
   for (auto i = 0; i < subArrayOne; i++)
       leftArray[i] = array[left + i];
   for (auto j = 0; j < subArrayTwo; j++)
       rightArray[j] = array[mid + 1 + j];
   auto indexOfSubArrayOne = 0, // Initial index of first sub-array
   indexOfSubArrayTwo = 0; // Initial index of second sub-array
   int indexOfMergedArray = left; // Initial index of merged array
       
           // Merge the temp arrays back into array[left..right]
           while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo) {
               if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) {
                   array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
                   indexOfSubArrayOne++;
               }
               else {
                   array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
                   indexOfSubArrayTwo++;
               }
               indexOfMergedArray++;
           }
           // Copy the remaining elements of
           // left[], if there are any
           while (indexOfSubArrayOne < subArrayOne) {
               array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
               indexOfSubArrayOne++;
               indexOfMergedArray++;
           }
           // Copy the remaining elements of
           // right[], if there are any
   while (indexOfSubArrayTwo < subArrayTwo)
   {
       array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
       indexOfSubArrayTwo++;
       indexOfMergedArray++;
   }
}
void mergeSort(int array[], int const begin, int const end)
{
   if (begin >= end)
   {
       return; // Returns recursively    
   }
   auto mid = begin + (end - begin) / 2;
   mergeSort(array, begin, mid);
   mergeSort(array, mid + 1, end);
   merge(array, begin, mid, end);
}
void Mergesorter()
{
   for(int i=0;i<n;i++)
   {
       arr[i]=arr_temp[i];
   }
   mergeSort(arr, 0, n-1);
   ofstream fout;
   fout.open("SortMerge.TXT");
   for(int i=0;i<n;i++)
   {
       fout<<arr[i]<<" ";
   }
   cout<<"Contents copied in SortMerge.TXT";
   fout.close();
}

void swap(int *a, int *b) 
{
  int t = *a;
  *a = *b;
  *b = t;
}

int partitionmidpiv(int array[], int low, int high) 
{
   int x;
   x=(low+high)/2;
  // select the rightmost element as pivot
  int pivot = array[x];
  // pointer for greater element
  int i = (low - 1);
   // traverse each element of the array
  // compare them with the pivot
  for (int j = low; j < high; j++) 
  {
    if (array[j] < pivot) //why < and not <=
   {
    // if element smaller than pivot is found
    // swap it with the greater element pointed by i
      i++;
    // swap element at i with element at j
      swap(&array[i], &array[j]);
    }
  }
  // swap pivot with the greater element at i
  swap(&array[i + 1], &array[x]);
  // return the partition point
  return (i+1);
}
void quickSortmidpiv(int array[], int low, int high)
{
  if (low < high)
  {
      
    // find the pivot element such that
    // elements smaller than pivot are on left of pivot
    // elements greater than pivot are on righ of pivot
    int pi = partitionmidpiv(array, low, high);

    // recursive call on the left of pivot
    quickSortmidpiv(array, low, pi - 1);

    // recursive call on the right of pivot
    quickSortmidpiv(array, pi + 1, high);
  }
}
void QuickSortMidPiv()
{
   for(int i=0;i<n;i++)
   {
       arr[i]=arr_temp[i];
   }
   quickSortmidpiv(arr, 0, n-1);
   cout<<"\n\n\nQuick Sort Middle pivot begins.\n\n\n";
   ofstream fout;
   fout.open("SortQuickMiddlepiv.TXT");
   for(int i=0;i<n;i++)
   {
       fout<<arr[i]<<" ";
   }
   cout<<"Contents copied in SortQuickMiddlepiv.TXT";
   fout.close();
}

int partition(int arr[], int low, int high) 
{ 
    int pivot = arr[high]; 
    int i = (low - 1); 
   for (int j = low; j <= high - 1; j++)
   {
        if (arr[j] <= pivot) { 
              i++; 
            swap(arr[i], arr[j]); 
        } 
    } 
    swap(arr[i + 1], arr[high]); 
    return (i + 1); 
}

int partition_r(int arr[], int low, int high) 
{ 
    // Generate a random number in between 
    // low .. high 
    srand(time(0)); 
    int random = low + rand() % (high - low); 
 
    // Swap A[random] with A[high] 
    swap(arr[random], arr[high]); 
 
    return partition(arr, low, high); 
}

void quickSortrandpiv(int arr[], int low, int high) 
{ 
    if (low < high) { 
 
        /* pi is partitioning index, arr[p] is now 
        at right place */
        int pi = partition_r(arr, low, high); 
 
        // Separately sort elements before 
        // partition and after partition 
        quickSortrandpiv(arr, low, pi - 1); 
        quickSortrandpiv(arr, pi + 1, high); 
    } 
}

void QuickSortRandPiv()
{
   for(int i=0;i<n;i++)
   {
       arr[i]=arr_temp[i];
   }
   quickSortrandpiv(arr, 0, n-1);
   cout<<"\n\n\nQuick Sort Random pivot begins.\n\n\n";
   ofstream fout;
   fout.open("SortQuickRandompiv.TXT");
   for(int i=0;i<n;i++)
   {
       fout<<arr[i]<<" ";
   }
   cout<<"Contents copied in SortQuickRandompiv.TXT";
   fout.close();
}
int main()
{
   int re=1;
   do{
       system("cls");
       using namespace std::chrono;
   gen();
   duplicateFile();
   
   //Insertion Sort
   steady_clock::time_point t1 = steady_clock::now();
   InsertionSort();
   steady_clock::time_point t2 = steady_clock::now();
   duration<double> time_span = duration_cast<duration<double>>(t2 - t1);
   cout<<"\n\n\n\n"<<time_span.count()<< " seconds" << endl;
   
   //Merge Sort
   steady_clock::time_point t3 = steady_clock::now();
   Mergesorter();
   steady_clock::time_point t4 = steady_clock::now();
   duration<double> time_span1 = duration_cast<duration<double>>(t4 - t3);
   cout<<"\n\n\n\n"<<time_span1.count()<< " seconds" << endl;
   
   //Quick Sort Middle Pivot
   steady_clock::time_point t5 = steady_clock::now();
   QuickSortMidPiv();
   steady_clock::time_point t6 = steady_clock::now();
   duration<double> time_span2 = duration_cast<duration<double>>(t6 - t5);
   cout<<"\n\n\n\n"<<time_span2.count()<< " seconds" << endl;
   
   //Quick Sort Random Pivot
   steady_clock::time_point t7 = steady_clock::now();
   QuickSortRandPiv();
   steady_clock::time_point t8 = steady_clock::now();
   duration<double> time_span3 = duration_cast<duration<double>>(t8 - t7);
   cout<<"\n\n\n\n"<<time_span3.count()<< " seconds" << endl;
   
   //Results
   ofstream fout;
   fout.open("Results.TXT",ios::app);
   fout<<"\n\n\nFor "<<n<<" integer data!\n\n";
   fout<<"Insertion Sort time             : "<<time_span.count()<<" seconds\n";
   fout<<"Merge Sort time                 : "<<time_span1.count()<<" seconds\n";
   fout<<"Quick Sort Middle as pivot time : "<<time_span2.count()<<" seconds\n";
   fout<<"Quick Sort Random pivot time    : "<<time_span3.count()<<" seconds\n\n\n";
   fout.close();
   cout<<"\n\n\nEnter 1 to run again and any other integer to close: ";
   cin>>re;
   }while(re==1);
   return 0;
}