Design and Analysis of Algorithms

176 Design and Analysis of Algorithms

A correct way to exchange A[i] and A[j] is

1 temp ← A[i];

2 A[i] ← A[j];

3 A[j] ← temp;

Since the exchange operation involves only i and j, I1(i) and I2(j) hold even after the exchange operation.

Thus, we have developed the partition algorithm and developed the proof of its correctness simultaneously.

The fi nal procedure is

Algorithm 7.8 Partition(A,i,j,m,n)

1 [ A[1...N], i and j by reference; all integers ]

2 local integer r, temp;

3 r

← A[(m+n)/2];

4 i

← m;

5 j

← n;

6 while i ≤

j do

7 while A[i] < r do

8 i

← i+1;

9 end

10 while r < A[j] do

11 j

← j-1;

12 end

13 if i

≤ j then