Array Partition

Array partition rearranges elements so that all elements satisfying a predicate come before those that do not. The operation runs in-place and does not require additional storage.

You use it as a primitive in selection, quicksort, filtering, and grouping tasks.

Problem

Given an array $A$ of length $n$ and a predicate $P(x)$, reorder the array so that:

• for all indices $i < k$, $P(A[i])$ holds
• for all indices $i \ge k$, $P(A[i])$ does not hold

for some partition index $k$.

Algorithm

Use a single pass with a boundary pointer.

partition(A, P):
    k = 0

    for i from 0 to length(A) - 1:
        if P(A[i]):
            swap A[i], A[k]
            k += 1

    return k

Example

Let

$$ A = [8, 3, 5, 1, 9] $$

Partition by even numbers:

$$ P(x): x \bmod 2 = 0 $$

step	i	action	array	k
1	0	8 even, swap with A[0]	[8, 3, 5, 1, 9]	1
2	1	3 odd	[8, 3, 5, 1, 9]	1
3	2	5 odd	[8, 3, 5, 1, 9]	1
4	3	1 odd	[8, 3, 5, 1, 9]	1
5	4	9 odd	[8, 3, 5, 1, 9]	1

Result:

$$ [8 \mid 3, 5, 1, 9] $$

Partition index:

$$ k = 1 $$

Correctness

At each step:

• indices $[0, k-1]$ contain elements that satisfy $P$
• indices $[k, i-1]$ contain elements that do not satisfy $P$

When $P(A[i])$ holds, swapping it into position $k$ extends the valid prefix. The invariant is preserved after each iteration. At the end, all elements before $k$ satisfy the predicate, and all others follow.

Complexity

operation	time
partition	$O(n)$

Space usage:

$$ O(1) $$

When to Use

Array partition is appropriate when:

• elements must be grouped by a condition
• in-place rearrangement is required
• order inside groups does not matter
• used as a step in quicksort or selection

It is less suitable when:

• stability is required
• original order must be preserved

Implementation

def partition(a, predicate):
    k = 0
    for i in range(len(a)):
        if predicate(a[i]):
            a[i], a[k] = a[k], a[i]
            k += 1
    return k

func Partition[T any](a []T, pred func(T) bool) int {
    k := 0
    for i := 0; i < len(a); i++ {
        if pred(a[i]) {
            a[i], a[k] = a[k], a[i]
            k++
        }
    }
    return k
}