代写四个算法小程序，不需要写具体编程代码，使用伪代码即可。
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:
MID-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.
