# 2.6 Partitioning

Partitioning rearranges an array so that elements are grouped by a predicate. The order inside each group may or may not be preserved, depending on the algorithm. This pattern appears in quicksort, selection, filtering, deduplication, stream compaction, and many in-place array transformations.

The central idea is to maintain a boundary between elements that are already classified and elements that are still unknown.

## Problem

Given an array `a` and a predicate `keep`, rearrange the array so that all elements satisfying the predicate appear before all elements that do not.

For example, given:

```text id="1z35yq"
[7, 2, 9, 1, 5, 3]
```

and predicate:

```text id="kmukrc"
x < 5
```

one valid partition is:

```text id="lmshrc"
[2, 1, 3, 7, 5, 9]
```

The values less than `5` appear first. The relative order inside each side is not required unless the partition is stable.

## Unstable In-Place Partition

The standard in-place partition scans with one pointer and maintains a write boundary.

```go id="mj3xvk"
func Partition(a []int, keep func(int) bool) int {
	write := 0

	for read := 0; read < len(a); read++ {
		if keep(a[read]) {
			a[write], a[read] = a[read], a[write]
			write++
		}
	}

	return write
}
```

After the function returns `p`:

```text id="y59zvc"
a[0:p] contains elements satisfying keep
a[p:] contains elements not satisfying keep
```

The function returns the split point, not a new array.

## Invariant

Before each iteration:

```text id="i6c5xk"
a[0:write] contains accepted elements
a[write:read] contains rejected elements
a[read:] has not been classified
```

When `keep(a[read])` is false, the rejected region grows by one.

When `keep(a[read])` is true, the element belongs in the accepted region. Swapping `a[read]` with `a[write]` places it at the end of the accepted region. Then `write++` extends that region.

This proves that after the scan, all accepted elements are before all rejected elements.

## Example

```go id="e86z7n"
a := []int{7, 2, 9, 1, 5, 3}

p := Partition(a, func(x int) bool {
	return x < 5
})

fmt.Println(a)
fmt.Println(p)
```

Possible output:

```text id="ml6c9y"
[2 1 3 7 5 9]
3
```

The exact order can differ because the algorithm is not stable.

## Stable Partition by Writing Forward

If the relative order of accepted elements matters, write them forward in scan order.

```go id="k21ssv"
func StableFilter(a []int, keep func(int) bool) []int {
	write := 0

	for read := 0; read < len(a); read++ {
		if keep(a[read]) {
			a[write] = a[read]
			write++
		}
	}

	return a[:write]
}
```

This preserves the order of kept elements, but it does not preserve the rejected elements in the returned slice.

Example:

```go id="qh9uct"
a := []int{7, 2, 9, 1, 5, 3}

b := StableFilter(a, func(x int) bool {
	return x < 5
})

fmt.Println(b)
```

Output:

```text id="w4ytre"
[2 1 3]
```

## Stable Two-Sided Partition

To preserve both accepted and rejected elements, use auxiliary storage.

```go id="d0d8m5"
func StablePartition(a []int, keep func(int) bool) ([]int, int) {
	out := make([]int, 0, len(a))

	for _, x := range a {
		if keep(x) {
			out = append(out, x)
		}
	}

	p := len(out)

	for _, x := range a {
		if !keep(x) {
			out = append(out, x)
		}
	}

	return out, p
}
```

This costs `O(n)` extra space, but the result is stable on both sides.

## Partition Around a Pivot

A frequent use is partitioning by comparison with a pivot.

```go id="e21xqb"
func PartitionLess(a []int, pivot int) int {
	write := 0

	for read := 0; read < len(a); read++ {
		if a[read] < pivot {
			a[write], a[read] = a[read], a[write]
			write++
		}
	}

	return write
}
```

After return:

```text id="rayd9p"
a[0:p] contains values less than pivot
a[p:] contains values greater than or equal to pivot
```

This form is useful for selection and quicksort, but quicksort usually needs a slightly more precise pivot placement.

## Lomuto Partition

Lomuto partition chooses a pivot value, usually the last element, and places it into its final sorted position.

```go id="zspzkp"
func LomutoPartition(a []int, lo, hi int) int {
	pivot := a[hi]
	i := lo

	for j := lo; j < hi; j++ {
		if a[j] < pivot {
			a[i], a[j] = a[j], a[i]
			i++
		}
	}

	a[i], a[hi] = a[hi], a[i]
	return i
}
```

Precondition:

```text id="bgbhzy"
0 <= lo <= hi < len(a)
```

Postcondition:

```text id="r2hguo"
a[lo:i] contains values less than pivot
a[i] is pivot
a[i+1:hi+1] contains values greater than or equal to pivot
```

Lomuto partition is simple, but it performs more swaps than some alternatives.

## Hoare Partition

Hoare partition scans inward from both ends.

```go id="j7r8ab"
func HoarePartition(a []int, lo, hi int) int {
	pivot := a[lo]
	i := lo - 1
	j := hi + 1

	for {
		for {
			i++
			if a[i] >= pivot {
				break
			}
		}

		for {
			j--
			if a[j] <= pivot {
				break
			}
		}

		if i >= j {
			return j
		}

		a[i], a[j] = a[j], a[i]
	}
}
```

Postcondition:

```text id="dbogs2"
a[lo:j+1] contains values less than or equal to pivot, up to partition order
a[j+1:hi+1] contains values greater than or equal to pivot, up to partition order
```

Hoare partition does not necessarily place the pivot at its final sorted index. It returns a split point suitable for recursive sorting.

## Three-Way Partition

Three-way partition is preferable when many elements equal the pivot.

```go id="zrjnnw"
func ThreeWayPartition(a []int, pivot int) (int, int) {
	lt := 0
	i := 0
	gt := len(a)

	for i < gt {
		if a[i] < pivot {
			a[lt], a[i] = a[i], a[lt]
			lt++
			i++
		} else if a[i] > pivot {
			gt--
			a[i], a[gt] = a[gt], a[i]
		} else {
			i++
		}
	}

	return lt, gt
}
```

After return:

```text id="o3mzbx"
a[0:lt] contains values less than pivot
a[lt:gt] contains values equal to pivot
a[gt:] contains values greater than pivot
```

The invariant is:

```text id="zm5h5o"
a[0:lt] < pivot
a[lt:i] == pivot
a[i:gt] unknown
a[gt:] > pivot
```

When a value greater than the pivot is swapped from the right side, `i` does not advance, because the new `a[i]` has not been classified yet.

## Complexity

All partition algorithms above perform one linear scan or two monotone scans.

Time complexity:

```text id="vm2zei"
O(n)
```

Extra space:

```text id="fw4kb7"
O(1)
```

for in-place partitioning, and:

```text id="gktru9"
O(n)
```

for stable two-sided partitioning with auxiliary storage.

## Common Pitfalls

Mixing the postconditions of Lomuto and Hoare partition causes incorrect quicksort implementations. Lomuto returns the final pivot index. Hoare returns a split point.

Advancing the scan index after swapping from the unknown right side in three-way partition skips an unclassified value.

Using `< pivot` instead of `<= pivot` changes where equal elements go. This matters for performance when duplicates are common.

Assuming unstable partition preserves order leads to subtle bugs. If order matters, use a stable variant.

Forgetting to return the split point makes the partition hard to use correctly in later algorithms.

## Takeaway

Partitioning is classification by boundary maintenance. The algorithm is correct when each region has a clear meaning and every operation preserves that meaning. Use ordinary in-place partition for speed, stable partition when order matters, and three-way partition when duplicates are frequent.