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

The original page permits

m = r

, but also indexes

a [m]

. The meaningful pivot-position contract is the stronger

l \leq m < r

, with

a [l .. m) < a [m]

and

a [m .. r) \geq a [m]

. Implement this two-way array partition by reserving the last entry as pivot:

PROCEDURE Partition(l, r: INTEGER): INTEGER;
VAR pivot, i, j, tmp: INTEGER;
BEGIN
  ASSERT(l < r);
  pivot := a[r-1];
  i := l; j := l;
  WHILE j < r-1 DO
    IF a[j] < pivot THEN
      tmp := a[i]; a[i] := a[j]; a[j] := tmp;
      i := i+1
    END;
    j := j+1
  END;
  tmp := a[i]; a[i] := a[r-1]; a[r-1] := tmp;
  RETURN i
END Partition;

The loop invariant is

l \leq i \leq j \leq r - 1, a [l .. i) < pivot, a [i .. j) \geq pivot, a [r - 1] = pivot .

(1)

The segment's multiset is preserved and entries outside

[l, r)

are unchanged. The unclassified part is

[j, r - 1)

. A smaller entry is swapped into the left group; if

i < j

, the displaced entry belongs to the greater-or-equal group. Otherwise the entry simply joins that group. The loop variant is

r - 1 - j

At exit the final swap installs the pivot at i, giving

m = i \in [l, r), a [l .. m) < a [m] \leq a [m .. r), T = Θ (r - l) .

(2)

A singleton segment is handled without loop iterations. Equality belongs on the pivot's right side, as required by the printed strict left inequality.

 Ancestors (11)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version

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

Solution

 Ancestors (11)

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

 Articles by others on the same topic (0)

 Discussion (0) New discussion