Design and Analysis of Algorithms

Design by Proof Rules 173

Implemented in this way, the exchange takes place without disturbing other array elements. This

completes the development of the Selection Sort algorithm, along with its proof of correctness. It is to be

noted that we used steps of the proof to guide us in the design of the algorithm. To that extent, this was a

proof-driven design.

The fi nal algorithm is:

Algorithm 7.6 SelectionSort(A, N)

1 [ array A[1...N] ]

2 for i ← 1 to N–1 do

3 m ← i;

4 for j ← i+1 to N do

5 if A[j] < A[m] then

6 m ← j;

7 end

8 end

9 temp ← A[i];

10 A[i] ← A[m];

11 A[m] ← temp;

12 end

7.6 EXAMPLE: PARTITION ()

We shall now design ...