Algorithm Design — One-Pass 0/1 Array Partition: 25-Comp-A4 Program Design and Data Structures, December 2018, Q9

Question 9: Algorithm Design — One-Pass 0/1 Array 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. An array of length $n$ holding only the values 0 and 1, in the arbitrary order shown above.

Find. The same array rearranged so every 0 precedes every 1, using exactly one traversal and no sorting routine or separate counting pass.

Approach. Maintain two pointers, left and right, starting at the two ends of the array and moving toward each other. Advance left past any 0 already in place, retreat right past any 1 already in place, and when left sits on a 1 and right sits on a 0, swap them — a two-pointer scheme that is a two-value special case of the Dutch national flag partition, and touches each array slot a bounded number of times.

Write the one-pass partition. The loop terminates the moment the pointers meet or cross, which happens after at most $n$ total pointer movements — one traversal, exactly as required, with no separate counting pass and no comparison-based sort involved.

#include <stdio.h>

void partition_zeros_ones(int a[], int n)
{
    int left = 0, right = n - 1, tmp;

    while (left < right) {
        if (a[left] == 0) {
            left++;                 /* already in place, move on */
        } else if (a[right] == 1) {
            right--;                /* already in place, move on */
        } else {                    /* a[left]==1 and a[right]==0: swap */
            tmp = a[left];
            a[left] = a[right];
            a[right] = tmp;
            left++;
            right--;
        }
    }
}

Trace the paper's own 15-element example. The input has nine 0's and six 1's (counted here only to check the result, not used by the algorithm itself, which never counts): $$n=15,\quad \#0=9,\quad \#1=6$$ The two pointers close in from both ends, swapping only the four out-of-place pairs, and converge with every 0 to the left of every 1: $$\boxed{0,0,0,0,0,0,0,0,0,1,1,1,1,1,1}$$ which matches the array printed as "Array at output" in the question, confirming the count of 9 zeros against 6 ones.

Question 9 — results
Quantity	Value
Array length $n$	15
Zeros / ones in the input	9 / 6
Partitioned output	0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
Passes over the array	1 (two pointers, no sort, no counting pass)

Concept & Theory

Topic. Two-pointer in-place partitioning — the two-value special case of the Dutch national flag algorithm.

Key relations. Maintaining the loop invariant "everything left of left is 0, everything right of right is 1" and swapping only when both pointers sit on an out-of-place value bounds total work to $O(n)$ with $O(1)$ extra space.

Why this works. Each of left and right only ever moves inward, and every iteration strictly advances at least one of them, so the loop runs at most $n$ iterations total — a single traversal, even though left and right are each, individually, scanning from a different end. No count of 0's or 1's is ever needed because the invariant itself guarantees the final split point is exactly where the two pointers meet.

Common pitfall. Writing a two-pass solution (count the 0's, then overwrite the array) — disallowed here twice over, both as "counting" and as a second traversal; or swapping unconditionally on every iteration without first checking whether a[left]/a[right] are already correctly placed, which produces extra unnecessary swaps but is not itself incorrect, only wasteful.

Source. Cormen et al., Introduction to Algorithms, 4th ed., §7.3 (partitioning, as used in quicksort's partition step, specialised here to two values); Weiss, Data Structures and Algorithm Analysis in C, 2nd ed., ch. 1 (in-place array algorithms).

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

Question 9: Algorithm Design — One-Pass 0/1 Array Partition (20 marks)