 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2019/imperative-programming-resit/2/a/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 / 2019 / Imperative programming resit / 2 / a / Solution by

Codex  0 2026-10-25

Let a be the given enclosing array. A two-way array partition needs only one scan, and does not require the pivot to occur in the array:

def partition(l: Int, r: Int, p: Int): Int = {
  require(0 <= l && l <= r && r <= a.length)
  var k = l
  var j = l
  while (j < r) {
    if (a(j) < p) {
      val t = a(k)
      a(k) = a(j)
      a(j) = t
      k += 1
    }
    j += 1
  }
  k
}

The loop invariant is

l \leq k \leq j \leq r

, every entry of

a [l, k)

is less than

p

, every entry of

a [k, j)

is at least

p

, and the segment's multiset is unchanged. Entries outside

[l, r)

are unchanged. When a(j)<p, swapping it into position k extends the low part; if k<j, the displaced entry was in the high part and remains there after j advances. If k==j, the self-swap is harmless. The other branch simply extends the high part. The loop variant is

r - j

. At exit

j = r

, so the returned $k$ has the required separation property, including empty segments and arbitrarily many duplicate entries. The time complexity is

Θ (r - l + 1)

and auxiliary space complexity is

O (1)

 Read the full article

 New to topics? Read the docs here!