The OpenD Programming Language

pivotPartition

mir ndslice sorting

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...
    template pivotPartition(alias less = "a < b")
    @trusted
    @fmamath
    static if(__traits(isSame, naryFun!less, less))
    size_t
    pivotPartition
    (
    Iterator
    size_t N
    SliceKind kind
    )
    (
    Slice!(Iterator, N, kind) slice
    ,
    size_t pivot
    )

    Members

    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]));

    See Also

    Engineering of a Quicksort Partitioning Algorithm, D. Abhyankar, Journal of Global Research in Computer Science, February 2011. ACCU 2016 Keynote, Andrei Alexandrescu.

    Meta

    Source

    See Implementation

    mir ndslice sorting functionstemplates
    Page generated by adrdox