Enum std.algorithm.mutation.SwapStrategy
Defines the swapping strategy for algorithms that need to swap
elements in a range (such as partition and sort). The strategy
concerns the swapping of elements that are not the core concern of the
algorithm. For example, consider an algorithm that sorts [ "abc",
"b", "aBc" ] according to toUpper(a) < toUpper(b). That
algorithm might choose to swap the two equivalent strings "abc"
and "aBc". That does not affect the sorting since both `$D(
"abc", "aBc", "b" ]) and [ "aBc", "abc", "b" ] are valid
outcomes.
enum SwapStrategy
: int { ... }
Some situations require that the algorithm must NOT ever change the
relative ordering of equivalent elements (in the example above, only
[ "abc", "aBc", "b" ] would be the correct result). Such
algorithms are called stable. If the ordering algorithm may swap
equivalent elements discretionarily, the ordering is called unstable.
Yet another class of algorithms may choose an intermediate tradeoff by being stable only on a well-defined subrange of the range. There is no established terminology for such behavior; this library calls it semistable.
Generally, the stable ordering strategy may be more costly in
time and/or space than the other two because it imposes additional
constraints. Similarly, semistable may be costlier than unstable. As (semi-)stability is not needed very often, the ordering
algorithms in this module parameterized by SwapStrategy all
choose SwapStrategy as the default.
Enum members
| Name | Description |
|---|---|
semistable
|
In algorithms partitioning ranges in two, preserve relative ordering of elements only to the left of the partition point. |
stable
|
Preserve the relative ordering of elements to the largest extent allowed by the algorithm's requirements. |
unstable
|
Allows freely swapping of elements as long as the output satisfies the algorithm's requirements. |
Example
int[] a = [0, 1, 2, 3];
writeln(remove!(SwapStrategyExample
import std