# Introduction to Algorithms:

Test on Selection Sort

### Paul Taylor

### 12 March 2001

**You have 50 minutes.**
The discussion is entirely about the *outer* loop of the algorithm,
*i.e*. the `sort` method itself..
public int[] sort (int[] A) {
int n=array.length;
int j=0;
while (j<n) {
int k = where_is_min (A, j);
int x = A[j];
A[j] = A[k];
A[k] = x;
j++;
}
return array;
}

In order to eliminate any discussion of the inner loop,
this makes use of the following private method.
private int where_is_min (int A[], int after) {
int size = array.length;
int position = after;
int result = after;
int value = Integer.MAX_VALUE;
while (position < size) {
if (A[position] < value) {
result = position;
value = A[position];
}
position++;
}
return result;
}

(a) State, in one English sentence, the **idea** of selection sort.
[1 mark]
(b) Draw a *loop invariant* diagram to show all of the pointers
(indices) into the array that you would use to code (the outer loop of)
the selection sort algorithm.
It should indicate typical positions of these pointers
during the execution of the loop,
and what is known about the values in the segments
into which the pointers divide the array.
There should be *four* parts to the diagram:
initial, typical, next and final,
and the relationships between these should be clearly indicated.
Hint: there are *three* logical conditions in the loop invariant.
[**5 marks**]
(c) How do you know that *each of the three conditions*
in the loop invariant (b) is justified
when the loop is entered for the first time,
*i.e*. just after the initialisation of the pointers?
[1 mark]
(d) What logical property,
relating `A[j]` to the rest of the array `A`,
is true after the following code has been executed,
assuming that `(j < A.length)`?
int k = where_is_min (A, j);
int x = A[j];
A[j] = A[k];
A[k] = x;

Write your answer in logical notation, paying close attention to whether
strict ( < ) or non-strict ( ≤ ) inequalities are required.
[1 mark]
(e) Assuming that the loop invariant in (b) was valid at the beginning
of the execution of a particular iteration of the body of the loop,
prove that (*each of the three conditions* in) the loop invariant is
valid again after the body of the loop has been executed once.
You must state clearly where the following things are used in the proof:
- each of the three conditions that make up the loop invariant that
was assumed to be true at the top of the loop,
- your answers to part (d), and
- the actual code overleaf.

[**5 marks**]
(f) How do you know *that* the loop terminates,
rather than continuing forever?
[1 mark]
(g) What logical property is true when the loop has terminated,
that you know simply because the loop has indeed terminated?
[1 mark]
(h) Putting (g) together with the loop invariant,
explain what can you deduce when the loop has terminated, and why.
[1 mark]
This is
`www.PaulTaylor.EU/algorithms/test12mar.html`
and it was derived from `algorithms/test12mar.tex`
which was last modified on 21 July 2007.