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:
[7, 2, 9, 1, 5, 3]and predicate:
x < 5one valid partition is:
[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.
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:
a[0:p] contains elements satisfying keep
a[p:] contains elements not satisfying keepThe function returns the split point, not a new array.
Invariant
Before each iteration:
a[0:write] contains accepted elements
a[write:read] contains rejected elements
a[read:] has not been classifiedWhen 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
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:
[2 1 3 7 5 9]
3The 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.
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:
a := []int{7, 2, 9, 1, 5, 3}
b := StableFilter(a, func(x int) bool {
return x < 5
})
fmt.Println(b)Output:
[2 1 3]Stable Two-Sided Partition
To preserve both accepted and rejected elements, use auxiliary storage.
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.
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:
a[0:p] contains values less than pivot
a[p:] contains values greater than or equal to pivotThis 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.
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:
0 <= lo <= hi < len(a)Postcondition:
a[lo:i] contains values less than pivot
a[i] is pivot
a[i+1:hi+1] contains values greater than or equal to pivotLomuto partition is simple, but it performs more swaps than some alternatives.
Hoare Partition
Hoare partition scans inward from both ends.
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:
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 orderHoare 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.
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:
a[0:lt] contains values less than pivot
a[lt:gt] contains values equal to pivot
a[gt:] contains values greater than pivotThe invariant is:
a[0:lt] < pivot
a[lt:i] == pivot
a[i:gt] unknown
a[gt:] > pivotWhen 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:
O(n)Extra space:
O(1)for in-place partitioning, and:
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.