pivotPartition

Partitions slice around pivot using comparison function less, algorithm akin to Hoare partition. Specifically, permutes elements of slice and returns an index k < slice.length such that:

$(UL

slice[pivot] is swapped to slice[k]

More...

size_t pivotPartition(Slice!(Iterator, N, kind) slice, size_t pivot)
template pivotPartition(alias less = "a < b")
@trusted
@optmath
static if(__traits(isSame, naryFun!less, less))
size_t
pivotPartition
(
Iterator
size_t N
SliceKind kind
)
(
Slice!(Iterator, N, kind) slice
,
size_t pivot
)
alias pivotPartition = .pivotPartition!(naryFun!less)

Members

Aliases

pivotPartition alias pivotPartition = .pivotPartition!(naryFun!less): Undocumented in source.

Functions

pivotPartition size_t pivotPartition(Slice!(Iterator, N, kind) slice, size_t pivot)

Parameters

less: The predicate used for comparison

Return Value

The new position of the pivot

Detailed Description

All elements e in subrange slice[0 .. k] satisfy !less(slice[k], e) (i.e. slice[k] is greater than or equal to each element to its left according to predicate less)

All elements e in subrange slice[k .. $] satisfy !less(e, slice[k]) (i.e. slice[k] is less than or equal to each element to its right according to predicate less)

)

If slice contains equivalent elements, multiple permutations of slice may satisfy these constraints. In such cases, pivotPartition attempts to distribute equivalent elements fairly to the left and right of k such that k stays close to slice.length / 2.

Examples

pivotPartition with 1-dimensional Slice

import mir.ndslice.slice: sliced;
import mir.algorithm.iteration: all;

auto x = [5, 3, 2, 6, 4, 1, 3, 7].sliced;
size_t pivot = pivotPartition(x, x.length / 2);

assert(x[0 .. pivot].all!(a => a <= x[pivot]));
assert(x[pivot .. $].all!(a => a >= x[pivot]));

pivotPartition with 2-dimensional Slice

import mir.ndslice.fuse: fuse;
import mir.ndslice.topology: flattened;
import mir.algorithm.iteration: all;

auto x = [
    [5, 3, 2, 6],
    [4, 1, 3, 7]
].fuse;

size_t pivot = pivotPartition(x, x.elementCount / 2);

auto xFlattened = x.flattened;
assert(xFlattened[0 .. pivot].all!(a => a <= xFlattened[pivot]));
assert(xFlattened[pivot .. $].all!(a => a >= xFlattened[pivot]));