// I NEED HELP CREATING A TEST MAIN FOR MY SORTING ALGORITHIMS BASED OF THE CONDITIONS BELOW

//Quick.h

#pragma once

#include

#include

#include

using namespace std;

static void partition(int data[], size_t n, size_t& pivot_index);

void quicksort(int data[], size_t n);

// -----------------------------------------------------------------

//Quick.cpp

#include "Quick.h"

#include

#include

#include

#include

#include

using namespace std;

static void partition(int data[], size_t n, size_t& pivot_index)

{

if (n > 1) {

int pivot = data[0];

int too_big_index = 1;

int too_small_index = n - 1;

while (too_big_index <= too_small_index) {

while ((too_big_index < n) && (data[too_big_index] <= pivot)) {

too_big_index++;

}

while (data[too_small_index] > pivot) {

too_small_index--;

}

if (too_big_index < too_small_index) {

int temp = data[too_big_index];

data[too_big_index] = data[too_small_index];

data[too_small_index] = temp;

}

}

pivot_index = too_small_index;

data[0] = data[pivot_index];

data[pivot_index] = pivot;

}

}

void quicksort(int data[], size_t n)

{

size_t pivot_index;

size_t n1;

size_t n2;

if (n > 1) {

partition(data, n, pivot_index);

n1 = pivot_index;

n2 = n - n1 - 1;

quicksort(data, n1);

quicksort((data + pivot_index + 1), n2);

}

}

static void selectionsort(int data[], size_t n)

{

size_t i, j, index_of_largest;

int largest;

if (n == 0)

return;

for (i = n - 1; i > 0; --i)

{

largest = data[0];

index_of_largest = 0;

for (j = 1; j <= i; ++j)

{

if (data[j] > largest)

{

largest = data[j];

index_of_largest = j;

}

}

swap(data[i], data[index_of_largest]);

}

}

static void swap(size_t& a, size_t& b) {

size_t temp = a;

a = b;

b = temp;

}

// -----------------------------------------------------------------

//main.cpp

/*

1. Generate int arrays with N(N up to 1000000) random integers(where the numbers are from 0 to N).Sort them with Selection Sort algorithm as described in class.

Record the timing in each case.

Compare with Quick Sort as developed by you.

Use the high_resolution_clock::time_point in the library for the timing measurements.

Also, sum all the elements in the array mod N(where N = the size of the array) to convince yourself that all the elements are still in the array after the sorting

(their sums must be the same).

2. Generate an int array of 1000000 elements containing the values of

data[0] = 0

data[1] = 0

data[999999] = 999999. Now sort this array with Quick Sort with different pivots :

Compare the performance of Quick Sort using

(a)the first element as the pivot(this will give you the worst case performance) and

(b)a better choice of a pivot is to take the middle value of 3 randomly chosen elements in the array.

*/