SKEDSOFT

Design Analysis Of Algorithm

Line 3 chooses a random number between 1 and n3. We use a range of 1 to n3 to make it likely that all the priorities in P are unique. Let us assume that all the priorities are unique.

The time-consuming step in this procedure is the sorting in line 4. After sorting, if P[i] is the jth smallest priority, then A[i] will be in position j of the output. In this manner we obtain a permutation. It remains to prove that the procedure produces a uniform random permutation, that is, that every permutation of the numbers 1 through n is equally likely to be produced.

Lemma 5.4: Procedure PERMUTE-BY-SORTING produces a uniform random permutation of the input, assuming that all priorities are distinct

Proof: We start by considering the particular permutation in which each element A[i] receives the ith smallest priority. We shall show that this permutation occurs with probability exactly 1/n!. For i = 1, 2, ..., n, let Xi be the event that element A[i] receives the ith smallest priority. Then we wish to compute the probability that for all i, event Xi occurs, which is

Pr {X1X2X3 ∩ ··· ∩ Xn-1Xn}.

this probability is equal to: Pr {X1} · Pr{X2 | X1} · Pr{X3 | X2X1} · Pr{X4 | X3X2X1}

Pr{Xi | Xi-1Xi-2 ∩ ··· ∩ X1} Pr{Xn | Xn-1 ∩ ··· ∩ X1}.

We have that Pr {X1} = 1/n because it is the probability that one priority chosen randomly out of a set of n is the smallest. Next, we observe that Pr {X2 | X1} = 1/(n - 1) because given that element A[1] has the smallest priority, each of the remaining n - 1 elements has an equal chance of having the second smallest priority. In general, for i = 2, 3, ..., n, we have that Pr {Xi | Xi-1Xi-2 ∩ ··· ∩ X1} = 1/(n - i 1), since, given that elements A[1] through A[i - 1] have the i - 1 smallest priorities (in order), each of the remaining n - (i - 1) elements has an equal chance of having the ith smallest priority. Thus, we have

and we have shown that the probability of obtaining the identity permutation is 1/n!.

We can extend this proof to work for any permutation of priorities. Consider any fixed permutation σ = < σ(1), σ(2), ..., σ(n) > of the set {1, 2, ..., n}. Let us denote by ri the rank of the priority assigned to element A[i], where the element with the jth smallest priority has rank j. If we define Xi as the event in which element A[i] receives the σ(i)th smallest priority, or ri = σ(i), the same proof still applies. Therefore, if we calculate the probability of obtaining any particular permutation, the calculation is identical to the one above, so that the probability of obtaining this permutation is also 1/n!.

Lemma 5.5: Procedure RANDOMIZE-IN-PLACE computes a uniform random permutation.

Proof: We use the following loop invariant:

  • Just prior to the ith iteration of the for loop of lines 2-3, for each possible (i - 1)-permutation, the subarray A[1 .. i - 1] contains this (i - 1)-permutation with probability (n - i 1)!/n!.

We need to show that this invariant is true prior to the first loop iteration, that each iteration of the loop maintains the invariant, and that the invariant provides a useful property to show correctness when the loop terminates.

  • Initialization:Consider the situation just before the first loop iteration, so that i = 1. The loop invariant says that for each possible 0-permutation, the sub-array A[1 .. 0] contains this 0-permutation with probability (n - i 1)!/n! = n!/n! = 1. The subarray A[1 .. 0] is an empty subarray, and a 0-permutation has no elements. Thus, A[1 .. 0] contains any 0-permutation with probability 1, and the loop invariant holds prior to the first iteration.
  • Maintenance:We assume that just before the (i - 1)st iteration, each possible (i - 1)-permutation appears in the subarray A[1 .. i - 1] with probability (n - i 1)!/n!, and we will show that after the ith iteration, each possible i-permutation appears in the subarray A[1 .. i] with probability (n - i)!/n!. Incrementing i for the next iteration will then maintain the loop invariant.

Let us examine the ith iteration. Consider a particular i-permutation, and denote the elements in it by <x1, x2, ..., xi>. This permutation consists of an (i - 1)-permutation <x1, ..., xi-1> followed by the value xi that the algorithm places in A[i]. Let E1 denote the event in which the first i - 1 iterations have created the particular (i - 1)-permutation <x1,..., xi-1> in A[1 .. i - 1]. By the loop invariant, Pr {E1} = (n - i 1)!/n!. Let E2 be the event that ith iteration puts xi in position A[i]. The i-permutation <x1, ..., xi> is formed in A[1 .. i] precisely when both E1 and E2 occur, and so we wish to compute Pr {E2E1}. we have

Pr {E2E1} = Pr{E2 | E1}Pr{E1}.

The probability Pr {E2 | E1} equals 1/(n-i 1) because in line 3 the algorithm chooses xi randomly from the n - i 1 values in positions A[i .. n]. Thus, we have

  • Termination:At termination, i = n 1, and we have that the subarray A[1 .. n] is a given n-permutation with probability (n - n)!/n! = 1/n!.

Thus, RANDOMIZE-IN-PLACE produces a uniform random permutation.