Solution

Maintain a processed prefix split into values below the pivot and values at least the pivot. The remaining suffix has not yet been classified. Here a and N are the given array and its length.

def partition(l: Int, r: Int, p: Int): Int = {
  require(0 <= l && l <= r && r <= N)
  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, a [l .. k) < p, a [k .. j) \geq p .

(1)

In addition, the active segment remains a permutation of its original contents, and every entry outside it remains unchanged. If a(j) < p, swapping it with a(k) extends the first region; the displaced entry, when the two positions differ, already belongs in the second region. Otherwise only the second region grows. The loop variant is

r - j

. At termination

j = r

, so

a [l .. k) < p \leq a [k .. r), return k .

(2)

There are exactly

r - l

iterations, giving

O (r - l + 1)

time complexity and constant auxiliary space.

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 1 / a / Solution

 Ancestors (12)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 1 / a / Solution

 Ancestors (12)

 Discussion (0)  Subscribe (1) New discussion

 Articles by others on the same topic (0)

 Discussion (0) New discussion