For this question, please refer to code pasted at the bottom.

In class we derived a formula for the number of item comparisons performed by quicksort in the best case, when the array size is a power of 2. The formula was only approximate because the recurrence T(n) = 2T(n/2) + n - 1 equates n/2-1 with n/2 for one of the two instances of T(n/2).

In this exercise you'll derive an exact formula for the number of item comparisons for array sizes equal to one less than a power of 2 (1, 3, 7, 15, 31 etc). That means we can express the array size as 2^k - 1 where k is a positive integer.

a) In the best case, partition returns a value equal to the average of low and high. When the array size it odd, that means, the recursive calls to quicksort1 will be passed subarrays of exactly equal size, (adding up to one less than the original subarray size) . Use this fact to complete the recurrence below. Don't use n in the expansion, just stick to expressions involving k. (We'll translate back to a function of n in Part d.)

T(2¹- 1) = ____________________________ (Of course this is the same as T(1).)

T(2^k - 1) = ____________________________ (For k > 1.)

b) Use your work in Part a to find T(1), T(3), T(7) and finally T(15). Show work.

c) Solve the recurrence in Part a using the approach from lecture. That means you'll expand what's in the second blank of Part a, then expand again and so on to reveal a pattern. Extrapolate the pattern to get a summation and finally a formula. As a check, plug in k = 1, 2, 3 and 4 to your formula. The answers should match what you got in Part b.

d) Let n = 2^k - 1. Express your formula, from part c in terms of n. T(n) = __________________________. Is this expression big Theta of nlog(n)? ____________ Why or why not?

e) In the code below, find a rearrangement of a4 so that the number of item comparisons agrees with your answer for T(15). Attach a .cpp with the edited program and a screenshot of your command window to prove that your rearrangement gives the desired count. Of course the other counts should match results from Part b as well.

Submit three files: A PDF of your work for parts a, b, c and d and the two files as instructed in Part e.

________________________________________________________________________________________

#include

using namespace std;

int counter;

int partition(int a[], int low, int high) {

int x = a[low];

bool highTurn = true;

while (low < high) {

counter++; // to count item comparisons highlighted in green

if (highTurn)

if (a[high] >= x) high--;

else {

a[low++] = a[high];

highTurn = false;

}

else

if (a[low] <= x) low++;

else {

a[high--] = a[low];

highTurn = true;

}

}

a[low] = x;

return low;

}

void quicksort1(int a[], int start, int end) {

if (start >= end) return;

int mid = partition(a, start, end);

quicksort1(a, start, mid - 1);

quicksort1(a, mid + 1, end);

}

void quicksort(int a[], int length) {

quicksort1(a, 0, length - 1);

}

void test(int array[], int length) {

counter = 0;

quicksort(array, length);

cout << "For length = " << length << ", counter = " << counter << endl;

}

int main() {

// Array contents for a1, a2, a3 give best case counts for their respective sizes.

int a1[] = { 0 }, // Array size 2^1 - 1

a2[] = { 1, 0, 2 }, // Array size 2^2 - 1

a3[] = { 3, 0, 2, 1, 5, 4, 6 }, // Array size 2^3 1

// Edit the line below so that a4 gives a best case count. Reorder the original values 0, 1, ..., 13, 14.

a4[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }; // Array size 2^4 1

test(a1, 1);

test(a2, 3);

test(a3, 7);

test(a4, 15);

return 0;

}