Search
View source code
Display the source code in std/algorithm/mutation.d from which this page was generated on github.
Report a bug
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.

# 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.unstable` as the default.

## Enum members

NameDescription
`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]
``````