Question 9 of 9: Algorithm Design — One-Pass Partition of a Binary Array

Question 9: Algorithm Design — One-Pass Partition of a Binary Array (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. An array of length $n$ whose elements take only the values 0 and 1, a worked 15-element example, and three explicit constraints: no sorting routine, no counting pass, and one traversal only.

Find. An algorithm and program that rearranges the array in place so that every 0 precedes every 1, within those constraints.

Approach. Run two indices inwards from the two ends, advancing whichever already sees a correctly placed value and exchanging the pair when both are misplaced, until the indices meet.

1. See why the obvious methods are excluded, and what remains. Counting the zeros and then overwriting is banned by the question; a comparison sort is banned as well, and would cost $O(n \log n)$ for what is really a partition. What remains is the partition step of quicksort, specialised to a two-valued array — and it is both faster and simpler than either prohibited approach.
2. State the invariant that the algorithm maintains. Two indices $i$ and $j$ start at the two ends, and the algorithm preserves $$\boxed{a[0..i-1] \text{ are all } 0 \quad\text{and}\quad a[j+1..n-1] \text{ are all } 1}$$ Both regions are empty at the start, so the invariant holds trivially; the loop only ever extends them. When $i$ and $j$ meet, the unexamined middle has vanished and the two regions together are the whole array, which is the required result.
3. Derive the three cases. At each step only two elements are inspected. If $a[i] = 0$ it is already in the left region, so $i$ advances. Else if $a[j] = 1$ it is already in the right region, so $j$ retreats. Otherwise $a[i] = 1$ and $a[j] = 0$ — both are misplaced, and a single exchange puts both where they belong, after which both indices move. Every iteration therefore reduces the unexamined region by at least one, guaranteeing termination.
4. Confirm the constraints are met. The indices $i$ and $j$ between them visit each position at most once and never reverse, so the array is traversed exactly once: this is the “one pass” the question demands, even though two indices are in play. Nothing is counted, nothing is compared against a pivot, and no auxiliary array is used, so the extra space is $O(1)$ and the time is $\Theta(n)$ — optimal, since every element must be examined at least once.

   /* Move every 0 to the left and every 1 to the right, in ONE traversal.
      No sort, no counting pass, O(1) extra space. */
   void partition01(int a[], int n)
   {
       int i = 0;              /* everything strictly left of i is known to be 0 */
       int j = n - 1;          /* everything strictly right of j is known to be 1 */
       int t;
   
       while (i < j) {
           if (a[i] == 0) {
               i++;                        /* already on the correct side */
           } else if (a[j] == 1) {
               j--;                        /* already on the correct side */
           } else {
               /* a[i] == 1 and a[j] == 0: one exchange puts BOTH right */
               t = a[i];  a[i] = a[j];  a[j] = t;
               i++;
               j--;
           }
       }
   }

5. Trace the given example. On 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0, the pointer at the left skips the leading 0, stops at the 1 in position 1, while the pointer at the right skips nothing and stops at the 0 in position 14; they exchange. Three further exchanges follow, after which the pointers meet at position 9. The array is then $$\boxed{0\;0\;0\;0\;0\;0\;0\;0\;0\;1\;1\;1\;1\;1\;1}$$ which is the output the question prints: nine 0s followed by six 1s, matching the nine 0s and six 1s of the input. Only four exchanges were needed.
6. Note what is not preserved. The partition is not stable — the 0s and 1s do not keep their original relative order among themselves. For a two-valued array this is invisible, since all 0s are identical, but the distinction matters the moment the same routine is applied to records carrying a 0/1 key alongside other data, where a stable partition would require either extra space or a different algorithm.