[Algo] Exercise 7.1

Exercise 7.1-2
What value of q does PARTITION return when all elements in the array $A[p \ldots r]$ have the same value? Modify PARTITION so that $q = (p+r)/2$ when all elements in the array $A[p \ldots r]$ have the same value.
Solution:
When all the elements have the same value, PARTITION will return r. We modify line 4 to "do if (A[j] < x) or (A[j] == x and j mod 2 == 0)", so that PARTITION will return $q = (p+r)/2$.


Exercise 7.1-3
Give a brief argument that the running time of PARTITION on a subarray of size n is $\Theta(n)$.
Solution:
From line 3 to line 6, we can see that we have a constant number of operations within each loop.


Exercise 7.1-4
How would you modify QUICKSORT to sort into nonincreasing order?
Solution:
We could modify line 4 to "do if $A[j] \geq x$".