# Array Partition

# 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.

```id="array-partition"
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

```python id="array-partition-python"
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
```

```go id="array-partition-go"
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
}
```