Display the source code in std/algorithm/sorting.d from which this page was generated on github.

If you spot a problem with this page, click here to create a Bugzilla issue.

Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

Function `std.algorithm.sorting.partition`

Partitions a range in two using the given predicate. Specifically, reorders the range r = [left, rightclass="pln">RPAREN using swap such that all elements i for which predicate(i) is true come before all elements j for which predicate(j) returns false.


						
				Range partition(alias predicate, SwapStrategy ss, Range)
				(
				

				  Range r
				

				)
				

				if (ss == SwapStrategy.stable && isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range && hasSwappableElements!Range);
				

				

				Range partition(alias predicate, SwapStrategy ss = SwapStrategy.unstable, Range)
				(
				

				  Range r
				

				)
				

				if (ss != SwapStrategy.stable && isInputRange!Range && hasSwappableElements!Range);

Performs Ο(r.length) (if unstable or semistable) or Ο(r.length * log(r.length)) (if stable) evaluations of less and swap. The unstable version computes the minimum possible evaluations of swap (roughly half of those performed by the semistable version).

Parameters

Name	Description
predicate	The predicate to partition by.
ss	The swapping strategy to employ.
r	The random-access range to partition.

Returns

The right part of r after partitioning.

If ss == SwapStrategy.stable, partition preserves the relative ordering of all elements a, b in r for which `predicate(a) =$D( predicate(b)). If ss == SwapStrategy.semistable, partition preserves the relative ordering of all elements a, b in the left part of r for which predicate(a) == predicate(b).

Example

import std.algorithm.mutation : SwapStrategy;
import std.algorithm.searching : count, find;
import std.conv : text;
import std.range.primitives : empty;

auto Arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
auto arr = Arr.dup;
static bool even(int a) { return (a & 1) == 0; }
// Partition arr such that even numbers come first
auto r = partition!(even)(arr);
// Now arr is separated in evens and odds.
// Numbers may have become shuffled due to instability
writeln(r); // arr[5 .. $]
writeln(count!(even)(arr[0 .. 5])); // 5
assert(find!(even)(r).empty);

// Can also specify the predicate as a string.
// Use 'a' as the predicate argument name
arr[] = Arr[];
r = partition!(q{(a & 1) == 0})(arr);
writeln(r); // arr[5 .. $]

// Now for a stable partition:
arr[] = Arr[];
r = partition!(q{(a & 1) == 0}, SwapStrategy.stable)(arr);
// Now arr is [2 4 6 8 10 1 3 5 7 9], and r points to 1
assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] && r == arr[5 .. $]);

// In case the predicate needs to hold its own state, use a delegate:
arr[] = Arr[];
int x = 3;
// Put stuff greater than 3 on the left
bool fun(int a) { return a > x; }
r = partition!(fun, SwapStrategy.semistable)(arr);
// Now arr is [4 5 6 7 8 9 10 2 3 1] and r points to 2
assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1] && r == arr[7 .. $]);

Authors

Andrei Alexandrescu

License

Boost License 1.0.