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: [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.