Non-Reversing Permutation
The pseudocode in the textbook for RANDOMIZE-IN-PLACE (p. 126) generates a permutation of an array such that any ordering is equally likely. Write pseudocode for PERMUTE-WITHOUT-REVERSAL, which should generate any ordering with equal likelihood except for the exact reverse of the original ordering. In other words, if the original array is A = {1, 5, 3, 2, 4}, then any permutation should be possible with equal likelihood except for {4, 2, 3, 5, 1}, which should not be a possible result. Your algorithm should not use any additional storage beyond the original array and a fixed number of temporary variables (no temporary arrays). Hint: it may help to think about how to correctly implement PERMUTE-WITHOUT-IDENTITY from problem 5.3-2 in the textbook (p. 128), and think about how you might use that code as part of your implementation of PERMUTE-WITHOUT-REVERSAL.
Inversions and Insertion-Sort
An array A is said to have an inversion at (i, j). Exercise 5.2-5 in the text (p. 122) asks for the expected number of inversions in an array A if the elements of the array A are a uniform random permutation. The solution of exercise 5.2-5 is provided.
Let A be an array of integers with no repeated values. The rank of an element of A is the index at which the value appears in the sorted permutation of A. For example, if A = <17, 6, 10, 9>, then A has inversions at (1, 2), (1, 3), (1, 4), and (3, 4), for a total of 4 inversions. The ranks of the elements 17, 6, 10, and 9 are 4, 1, 3, and 2, respectively. Suppose all permutations of the ranks of values in A are equally likely.
Use the result of Exercise 5.2-5 to give a Θ bound on the average case running time of INSERTION-SORT (p. 18) on A (for the general case, not just the example above). Be sure to describe the relationship between the number of inversions in A and the running time of INSERTION-SORT on A.
Sorting Probabilities
For an array A (using 1-based indexing) containing the integers 1 through n in random order, in regard to sorting the integers into ascending order, answer the following (give an explanation for each answer):
- What is the probability before sorting that A[i] = i for all 1 ≤ i ≤ n?
- For any given j such that 1 ≤ j ≤ n, what is the probability before sorting that A[j] = j?
- What is the probability before sorting that A[k] ≠ k for all 1 ≤ k ≤ n?
- For a given value m, where 1 ≤ m ≤ n, what is the probability before sorting that A[i] = i for all 1 ≤ i ≤ m?
- If Q UICKSORT (p. 171) is used to sort A, what is the probability that the top-level call P ARTITION (A, 1, n) will result in a return value of either 1 or n?
Midpoint-Pivot Quicksort
Consider the pseudocode below for a version of quicksort which always picks the middle item to use as the pivot:1
2
3
4
5
6
7MID-QUICKSORT (A, p, r)
if p < r
mid = [(p + r)/2]
swap A[mid] with A[r] // move middle element to pivot
q = P ARTITION (A, p, r)
MID-QUICKSORT (A, p, q - 1)
MID-QUICKSORT (A, q + 1, r)
This code uses the version of P ARTITION on p. 171 of the textbook.
Find a permutation of the five numbers 11, 22, 33, 44, 55 which generates worst-case behavior when given as input to MID-QUICKSORT; that is, a sequence such that every partition result will have 0 elements in either the low or high range. Show the input, output, and q value for every call to P ARTITION using your worst-case input.