quicksort

#include <stdio.h>
#include <omp.h>
#include <vector>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <time.h>
#include <chrono>

using namespace std;
using namespace std::chrono;

#define VEC_SIZE 10000
#define GENERATOR_RANGE 50

int partition(vector<int> &data, int p, int r){
    int pivot = data[p];
    int left = p;
    int right = r;
    while (left < right){
        while (left < r && data[left] <= pivot) ++left;
        while (right >= 0 && data[right] > pivot) --right;
        if (left < right && left <r && right >= 0)
        {
            std::swap(data[left], data[right]);
        }
    }

    if (left < right && left <r && right >= 0)
    {
        std::swap(data[left], data[right]);
    }
    data[p] = data[right];
    data[right] = pivot;
    return right;
}

void ParallelQuickSort (vector<int> &dataList,  int nLower, int nUpper)
{
    if (nLower < nUpper)
    {
        int nSplit = partition (dataList, nLower, nUpper);
        omp_set_num_threads(2);
        #pragma omp parallel sections
        {
            #pragma omp section
            ParallelQuickSort (dataList, nLower, nSplit - 1);

            #pragma omp section
            ParallelQuickSort (dataList, nSplit + 1, nUpper);
        }
    }
}

void SerialQuickSort(vector<int> &dataList,  int nLower, int nUpper)
{
    if (nLower < nUpper)
    {
        int nSplit = partition (dataList, nLower, nUpper);
        SerialQuickSort (dataList, nLower, nSplit - 1);
        SerialQuickSort (dataList, nSplit + 1, nUpper);
    }
}

void random_num_generator(vector<int> &vec)
{
    for(int i=0;i<VEC_SIZE;i++)
    {
        vec.push_back(rand()%GENERATOR_RANGE);
    }
}


void start_parallel_quicksort(vector<int> &vec,double &parallel_run_time)
{
    double parallel_start_time;
    parallel_start_time=omp_get_wtime();
    #pragma omp parallel
    {
        #pragma omp single nowait
        ParallelQuickSort(vec,0,VEC_SIZE-1);
    }
    parallel_run_time=omp_get_wtime()-parallel_start_time;
}

void start_serial_quicksort(vector<int> &vec, duration<double> &serial_run_time)
{
    auto serial_start_time = high_resolution_clock::now();
    SerialQuickSort(vec,0,VEC_SIZE-1);
    auto serial_end_time=high_resolution_clock::now();
    serial_run_time=serial_end_time-serial_start_time;
}

void sort_verifier(vector<int> &vec)
{
    if(is_sorted(vec.begin(),vec.end()))
    {
        cout<<"sorted successfully"<<endl;
    }
    else
    {
        cout<<"sort failed"<<endl;
    }
}


int main()
{
    srand(time(NULL));
    double parallel_run_time;
    duration<double>serial_run_time;
    vector<int>vec,vec_duplicate;//duplicate=> for serial quicksort to run on and calculate time for comparison
    random_num_generator(vec);
    vec_duplicate=vec;

    start_parallel_quicksort(vec,parallel_run_time);
    sort_verifier(vec);

    start_serial_quicksort(vec_duplicate,serial_run_time);
    sort_verifier(vec_duplicate);
    cout<<"parallel time:"<<parallel_run_time<<" serial time:"<<serial_run_time.count()<<endl;

}