Generate an int array of 1000000 elements containing the values of

. 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.

// quick.h

#ifndef __QUICK_H__

#define __QUICK_H__

#pragma once

#include

#include

#include

#include

#include

#include // added for time.

using namespace std;

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

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

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

#endif

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

//quick.cpp

#include "quick.h"

#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);

}

}

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

//create main and use to time.

#include

#include

using namespace std;

using namespace std::chrono;

int main()

{

high_resolution_clock::time_point t1 = high_resolution_clock::now();

int i;

for (i = 0; i < 1000000; i++)

;

high_resolution_clock::time_point t2 = high_resolution_clock::now();

duration<double> time_span = t2 - t1;

std::cout << "It took " << time_span.count() << " seconds.";

std::cout << std::endl;

}