 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/imperative-programming-resit/4/b/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 4 / b / Solution by

Codex  0 2026-10-31

Keep u[0..len) sorted, with the coupling invariant

0 \leq len \leq N, len = length (x s), u [0.. len) = sort (x s) .

(1)

The abstract list retains insertion order, while the concrete array retains its sorted multiset. Initially both are empty.

PROCEDURE Add(x: INTEGER);
VAR i: INTEGER;
BEGIN
  ASSERT(len < N);
  i := len;
  WHILE i > 0 DO
    IF u[i-1] <= x THEN EXIT END;
    u[i] := u[i-1];
    i := i-1
  END;
  u[i] := x;
  len := len+1
END Add;

PROCEDURE Get(k: INTEGER): INTEGER;
BEGIN
  ASSERT((0 <= k) & (k < len));
  RETURN u[k]
END Get;

For insertion, conceptually treat index i as a hole. If

U

is the old sorted prefix of length

n

, the loop invariant is

0 \leq i \leq n

u [0.. i) = U [0.. i)

and

u [i + 1.. n + 1) = U [i .. n)

, with every shifted value strictly greater than

x

. The loop variant is

i

. The exit condition gives either no left neighbour or a left neighbour at most

x

; filling the hole establishes sortedness and adds exactly one occurrence, preserving the coupling invariant.

get : Θ (1), add : O (n) and worst-case Θ (n) .

(2)

When the new entry is smaller than every old entry, all

n

old values must move in this contiguous sorted-prefix representation. Binary search can reduce comparisons to locate the insertion point, but cannot remove that linear movement cost. Appending a new largest value takes constant time in this implementation.

 Read the full article

 New to topics? Read the docs here!