Question 8 of 9: Algorithm Design — One-Pass 0/1 Partition

Question 8: Algorithm Design — One-Pass 0/1 Partition (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. A length-$n$ array containing only 0s and 1s.

Find. The same array rearranged so every 0 precedes every 1, using one traversal and no sort, no counting pass.

Approach. This is the two-value case of the classic Dutch-national-flag partition: two pointers start at the two ends and move inward, each index examined at most once in total, swapping only when a 0 is found stranded on the right and a 1 stranded on the left.

1. State the two-pointer invariant. Maintain lo (scans forward from the left) and hi (scans backward from the right). Everything at or before lo's last confirmed position is already known to be 0; everything at or after hi's is already known to be 1. When a[lo]==0 it is already in place, so lo just advances; when a[hi]==1 it is already in place, so hi just retreats; only when a[lo]==1 and a[hi]==0 is a swap needed — one swap exchanges both elements into their correct halves at once. Crucially, each of the $n$ positions is inspected a bounded number of times before lo and hi cross, giving a single $O(n)$ pass with no separate counting step.
2. Write the program.

   #include <stdio.h>
   
   void partition01(int a[], int n)
   {
       int lo = 0, hi = n - 1, tmp;
       while (lo < hi) {
           if (a[lo] == 0) {
               lo++;
           } else if (a[hi] == 1) {
               hi--;
           } else {                    /* a[lo]==1 and a[hi]==0: swap into place */
               tmp = a[lo]; a[lo] = a[hi]; a[hi] = tmp;
               lo++; hi--;
           }
       }
   }
   
   int main(void)
   {
       int a[15] = {0,1,0,1,0,0,1,1,0,1,0,1,0,0,0};
       int i;
       partition01(a, 15);
       for (i = 0; i < 15; i++) printf("%d ", a[i]);
       printf("\n");
       return 0;
   }

3. Trace the paper's own 15-element example to confirm. The input 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0 holds nine 0's and six 1's (confirmed by direct count, not used by the algorithm itself); running the two-pointer sweep above moves every 1 rightward and every 0 leftward one swap at a time until lo and hi cross, producing nine 0's followed by six 1's — exactly the array the question prints as "array at output." $$\boxed{\text{partition}(\text{input}) = \underbrace{0,\ldots,0}_{9},\ \underbrace{1,\ldots,1}_{6}}$$