| Value | Meaning |
|---|---|
| unstable | Allows freely swapping of elements as long as the output satisfies the algorithm's requirements. |
| 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. |
int[] a = [0, 1, 2, 3]; assert(remove!(SwapStrategy.stable)(a, 1) == [0, 2, 3]); a = [0, 1, 2, 3]; assert(remove!(SwapStrategy.unstable)(a, 1) == [0, 3, 2]);
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]; assert(partition!(a => a > 3, SwapStrategy.stable)(arr) == [1, 2, 3]); assert(arr == [4, 5, 6, 7, 8, 9, 10, 1, 2, 3]); arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; assert(partition!(a => a > 3, SwapStrategy.semistable)(arr) == [2, 3, 1]); assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1]); arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; assert(partition!(a => a > 3, SwapStrategy.unstable)(arr) == [3, 2, 1]); assert(arr == [10, 9, 8, 4, 5, 6, 7, 3, 2, 1]);
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.
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.