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
["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!(SwapStrategy .stable)(a, 1)); // [0, 2, 3]
a = [0, 1, 2, 3];
writeln(remove!(SwapStrategy .unstable)(a, 1)); // [0, 3, 2]
Example
import std .algorithm .sorting : partition;
// Put stuff greater than 3 on the left
auto arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
writeln(partition!(a => a > 3, SwapStrategy .stable)(arr)); // [1, 2, 3]
writeln(arr); // [4, 5, 6, 7, 8, 9, 10, 1, 2, 3]
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
writeln(partition!(a => a > 3, SwapStrategy .semistable)(arr)); // [2, 3, 1]
writeln(arr); // [4, 5, 6, 7, 8, 9, 10, 2, 3, 1]
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
writeln(partition!(a => a > 3, SwapStrategy .unstable)(arr)); // [3, 2, 1]
writeln(arr); // [10, 9, 8, 4, 5, 6, 7, 3, 2, 1]