C++

1) Revises the function quickSort so that it always chooses the first item in the array as the pivot. Add a counter to the function partition that counts the number of comparisons that are made. Compare the behavior of the revised function with the original one (pivot should be selected using sortFirstMiddleLast algorithm), using arrays of various sizes. At what size array does the difference in the number of comparisons become significant? For which pivot selection strategy does the difference in the number of comparisons become significant? Compare your analysis with the actual running times and counter as a function of the input size n = 16, 32, 64, 128, 256, 512, 1024, 2048, 8192, 16384 and clock() function.)

2) Write a program to display the running time of the sorts (bubble, selection, insertion, merge, and quick sorts) described in this chapter. Test the sorts on array of various sizes. Arrays of the same size should contain identical entries. Compare your analysis with the actual running times of the input size n = 16, 32, 64, 128, 256, 512, 1024, 2048, 8192, 16384 and clock() function.)

I know I'm NOT EVEN CLOSE to being right or done but so far I have the following functions I don't think I did these right:

int partition(ItemType array, int first, int last)

{

int middle = first + (last - first) / 2;

sortFirstMidLast(array, first, middle, last);

swap(array[middle], array[first]);

int pivotIndex = first;

int pivot = array[pivotIndex];

int left = first + 1;

int right = last;

bool done = false;

while (!done)

{

while (array[left] < pivot)

left = left + 1;

while (array[right] > pivot)

right = right - 1;

if (left < right)

{

swap(left, right);

left = left + 1;

right = right - 1;

}

else

done = true;

}

swap(array[pivotIndex], array[left]);

pivotIndex = left;

return pivotIndex;

}

void quickSort(ItemType array, int first, int last)

{

if (first < last)

{

int pivotIndex = partition(array, first, last);

quickSort(array, first, pivotIndex - 1);

quickSort(array, pivotIndex + 1, last);

}

}

void sortFirstMidLast(ItemType array, int first, int middle, int last)

{

if (array[first] > array[middle])

{

swap(array[first], array[middle]);

}

if (array[middle] > array[last])

{

swap(array[middle], array[last]);

}

if (array[first] > array[middle])

{

swap(array[first], array[middle]);

}

}

void swap(int *x, int *y)

{

int temp = *x;

*x = *y;

*y = temp;

}