- array shift (already done in the model answer to the first test),
- linear search,
- binary search,
- selection sort,
- insertion sort (already done on this sheet),
- merge (the loop, not recursive merge-sort),
- split (as used in recursive quick-sort).

You are given an array

int[] A = new int[n];that has somehow been filled with

(c) How do you know that the loop invariant (a) is justified by the initialisation (b)?int j=0;(or 1)

The "typical" version of the loop invariant in the case(d) What is the condition that goes inside thej=0says that the "sorted" part is empty (or has exactly one element), so is trivially sorted, whilst the "untouched" part is the whole (or rest) of the array,i.e. that the array is in its original form.

(e) When the insertion sort algorithm was presented to you in lectures, two subroutines (methods) were used inside the main loop of the algorithm. Write the JAVA code that goes inside the body of the loop,while (j < n)

int x = A[j]; // the next "unsorted" entry int k = search (A, j, x); shift (A, k, k+1, j-k); A[k] = x; // re-insert the new entry j++;The pieces of code

(g) What is the specification of the second subroutine? Describe it in English, not logical notation.k = search (A, j, x)findsxinA[]beforej:

(k=0 ∨A[k−1] ≤x) ∧(0 ≤k≤j) ∧(x<A[k] ∨k=j)

(h) How do you know that the loop invariant (a) is validshift (A, k, k+1, j-k)shifts the segment of lengthj-kstarting atkto start atk+1, leaving the rest of the array ( <kand ≥j) as it was.

The shift and re-insertion effect a permutation on the array; in fact they perform a ((i) How do you know that the loop terminates?j−k+1)-cycle on the affected entries and the identity on the rest. The loop invariant, as assumed at the top of the loop, says that the segment to the left ofjwas sorted. Whenjhas been incremented, it delimits another such segment, containing an extra entry with valuexinserted before positionk; this is sorted because the specification of the search subroutine says that the appropriate inequalities hold. If you chose instead to use the in-line version of the code in part (p), you would have had to give a second loop invariant and proof for the inner loop.This would involve reproducing the whole of the answer to the first test!

The positive integer(j) What can you deduce from the loop condition (d) and the loop invariant (a) when the loop has terminated?n−jis reduced in each iteration.

When the loop(k) What is the total number of operations that are performed by the second subroutine throughout the execution of the insertion sort algorithm, in theconditionfails,j=n. The loopinvariantin this case says that the "sorted" part of the array is the whole of it, and the "untouched" part none. It also says that the array as it currently stands is a permutation of the original state. In other words, the array has been sorted as required.

In the worst case, where(l) What kind of data in the array give rise to the worst-case behaviour?k=0,shiftperformsjcomparisons and assignments on thejth call, totalling^{1}/_{2}n(n−1).

This happens when ∀(m) How many operations are performed in thej. ∀i<j.A[j] <A[i],i.e. when the array is reverse-sorted (without repetitions).

In the average case,(n) How many operations are performed in theA[j] is approximately the median of the sorted segment, soshifthas to do aboutj/2 assignments on thejth call, totalling approximatelyn^{2}/4.

In the best case,(o) In "k=j, so the loop inshiftis not executed. This happens when ∀j. ∀i<j.A[j] ≥A[i],i.e. the array was sorted (possibly with repetitions). To take advantage of this situation,searchmust return therightmostoccurrence ofx, otherwise any repetitions ofxwill get shifted unnecessarily. Linear search from the right will do this, but binary search will takenlognsteps altogether.

(p) It is, of course, more efficient to do the job of the two subroutines "in-line"O(n), because there are other steps in the main loop (and in the initialisation ofsearchandshift) that are performed once for each iteration of the main loop,i.e.ntimes.

int j=2; while (j<n) { int x = A[j]; int k = j; while (k > 0 && A[k-1] > x) { A[k] = A[k-1]; k--; } A[k] = x; j++; }

This is
`www.PaulTaylor.EU/algorithms/insertion_sort.html`
and it was derived from `algorithms/insertion_sort.tex`
which was last modified on 21 July 2007.