Menu

- Learn
- Documentation
  - Language Reference
  - Library Reference
  - Command-line Reference
  - Feature Overview
  - Articles
- Downloads
- Packages
- Community
  - Blog
  - Orgs using D
  - Twitter
  - Forums
  - IRC
  - Community Discord
  - Wiki
  - GitHub
  - Issues
  - Get involved
  - Contributors
  - Foundation
  - Security Team
  - Donate
  - Sponsors
- Resources
  - Tour
  - Books
  - Tutorials
  - Tools
  - Editors
  - IDEs
  - run.dlang.io
  - Visual D
  - Acknowledgments
  - D Style
  - Glossary
  - Sitemap

Search
Report a bug
If you spot a problem with this page, click here to create a Bugzilla issue.
Improve this page
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 a local clone.

# std.algorithm.sorting

This is a submodule of std.algorithm. It contains generic sorting algorithms.

Cheat Sheet
Function Name | Description
--- | ---
completeSort | If a = [10, 20, 30] and b = [40, 6, 15], then completeSort(a, b) leaves a = [6, 10, 15] and b = [20, 30, 40]. The range a must be sorted prior to the call, and as a result the combination std.range.chain(a, b) is sorted.
isPartitioned | isPartitioned!"a < 0"([-1, -2, 1, 0, 2]) returns true because the predicate is true for a portion of the range and false afterwards.
isSorted | isSorted([1, 1, 2, 3]) returns true.
isStrictlyMonotonic | isStrictlyMonotonic([1, 1, 2, 3]) returns false.
ordered | ordered(1, 1, 2, 3) returns true.
strictlyOrdered | strictlyOrdered(1, 1, 2, 3) returns false.
makeIndex | Creates a separate index for a range.
merge | Lazily merges two or more sorted ranges.
multiSort | Sorts by multiple keys.
nextEvenPermutation | Computes the next lexicographically greater even permutation of a range in-place.
nextPermutation | Computes the next lexicographically greater permutation of a range in-place.
nthPermutation | Computes the nth permutation of a range in-place.
partialSort | If a = [5, 4, 3, 2, 1], then partialSort(a, 3) leaves a[0 .. 3] = [1, 2, 3]. The other elements of a are left in an unspecified order.
partition | Partitions a range according to a unary predicate.
partition3 | Partitions a range according to a binary predicate in three parts (less than, equal, greater than the given pivot). Pivot is not given as an index, but instead as an element independent from the range's content.
pivotPartition | Partitions a range according to a binary predicate in two parts: less than or equal, and greater than or equal to the given pivot, passed as an index in the range.
schwartzSort | Sorts with the help of the Schwartzian transform.
sort | Sorts.
topN | Separates the top elements in a range, akin to Quickselect.
topNCopy | Copies out the top elements of a range.
topNIndex | Builds an index of the top elements of a range.

License:
Boost License 1.0.
Authors:
Andrei Alexandrescu

Source std/algorithm/sorting.d

alias `SortOutput` = std.typecons.Flag!"sortOutput".Flag;
  Specifies whether the output of certain algorithm is desired in sorted format.
  If set to `SortOutput`.no, the output should not be sorted.
  Otherwise if set to `SortOutput`.yes, the output should be sorted.
void `completeSort`(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Lhs, Rhs)(SortedRange!(Lhs, less) `lhs`, Rhs `rhs`)
if (hasLength!Rhs && hasSlicing!Rhs && hasSwappableElements!Lhs && hasSwappableElements!Rhs);
  Sorts the random-access range chain(`lhs`, `rhs`) according to predicate less.
  The left-hand side of the range `lhs` is assumed to be already sorted; `rhs` is assumed to be unsorted. The exact strategy chosen depends on the relative sizes of `lhs` and `rhs`. Performs Ο(lhs.length + rhs.length * log(rhs.length)) (best case) to Ο((lhs.length + rhs.length) * log(lhs.length + rhs.length)) (worst-case) evaluations of swap.
  Parameters:

  less | The predicate to sort by.
  ss | The swapping strategy to use.
  SortedRange!(Lhs, less) `lhs` | The sorted, left-hand side of the random access range to be sorted.
  Rhs `rhs` | The unsorted, right-hand side of the random access range to be sorted.

  Examples:

      import std.range : assumeSorted;
      int[] a = [ 1, 2, 3 ];
      int[] b = [ 4, 0, 6, 5 ];
      completeSort(assumeSorted(a), b);
      writeln(a); // [0, 1, 2]
      writeln(b); // [3, 4, 5, 6]

bool `isSorted`(alias less = "a < b", Range)(Range `r`)
if (isForwardRange!Range);
bool `isStrictlyMonotonic`(alias less = "a < b", Range)(Range `r`)
if (isForwardRange!Range);
  Checks whether a forward range is sorted according to the comparison operation less. Performs Ο(r.length) evaluations of less.
  Unlike `isSorted`, `isStrictlyMonotonic` does not allow for equal values, i.e. values for which both less(a, b) and less(b, a) are false.
  With either function, the predicate must be a strict ordering just like with `isSorted`. For example, using "a <= b" instead of "a < b" is incorrect and will cause failed assertions.
  Parameters:

  less | Predicate the range should be sorted by.
  Range `r` | Forward range to check for sortedness.

  Returns:
  true if the range is sorted, false otherwise. `isSorted` allows duplicates, `isStrictlyMonotonic` not.
  Examples:

      assert([1, 1, 2].isSorted);
      // strictly monotonic doesn't allow duplicates
      assert(![1, 1, 2].isStrictlyMonotonic);

      int[] arr = [4, 3, 2, 1];
      assert(!isSorted(arr));
      assert(!isStrictlyMonotonic(arr));

      assert(isSorted!"a > b"(arr));
      assert(isStrictlyMonotonic!"a > b"(arr));

      sort(arr);
      assert(isSorted(arr));
      assert(isStrictlyMonotonic(arr));

bool `ordered`(alias less = "a < b", T...)(T `values`)
if (T.length == 2 && is(typeof(binaryFun!less(`values`[1], `values`[0])) : bool) || T.length > 2 && is(typeof(`ordered`!less(`values`[0..1 + $ / 2]))) && is(typeof(`ordered`!less(`values`[$ / 2..$]))));
bool `strictlyOrdered`(alias less = "a < b", T...)(T `values`)
if (is(typeof(ordered!less(`values`))));
  Like isSorted, returns true if the given `values` are ordered according to the comparison operation less. Unlike isSorted, takes values directly instead of structured in a range.
  `ordered` allows repeated values, e.g. `ordered`(1, 1, 2) is true. To verify that the values are ordered strictly monotonically, use `strictlyOrdered`; `strictlyOrdered`(1, 1, 2) is false.
  With either function, the predicate must be a strict ordering. For example, using "a <= b" instead of "a < b" is incorrect and will cause failed assertions.
  Parameters:

  T `values` | The tested value
  less | The comparison predicate

  Returns:
  true if the values are ordered; `ordered` allows for duplicates, `strictlyOrdered` does not.
  Examples:

      assert(ordered(42, 42, 43));
      assert(!strictlyOrdered(43, 42, 45));
      assert(ordered(42, 42, 43));
      assert(!strictlyOrdered(42, 42, 43));
      assert(!ordered(43, 42, 45));
      // Ordered lexicographically
      assert(ordered("Jane", "Jim", "Joe"));
      assert(strictlyOrdered("Jane", "Jim", "Joe"));
      // Incidentally also ordered by length decreasing
      assert(ordered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe"));
      // ... but not strictly so: "Jim" and "Joe" have the same length
      assert(!strictlyOrdered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe"));

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);
  Partitions a range in two using the given predicate.
  Specifically, reorders the range `r` = [left, right) using swap such that all elements i for which predicate(i) is true come before all elements j for which predicate(j) returns false.
  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:

  predicate | The predicate to partition by.
  ss | The swapping strategy to employ.
  Range `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) == 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).
  Examples:

      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 .. $]);

size_t `pivotPartition`(alias less = "a < b", Range)(Range `r`, size_t `pivot`)
if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range && hasAssignableElements!Range);
  Partitions `r` around `pivot` using comparison function less, algorithm akin to Hoare partition.
  Specifically, permutes elements of `r` and returns an index k < `r`.length such that:
  - `r`[`pivot`] is swapped to `r`[k]
  - All elements e in subrange `r`[0 .. k] satisfy !less(`r`[k], e) (i.e. `r`[k] is greater than or equal to each element to its left according to predicate less)
  - All elements e in subrange `r`[k .. $] satisfy !less(e, `r`[k]) (i.e. `r`[k] is less than or equal to each element to its right according to predicate less)
  If `r` contains equivalent elements, multiple permutations of `r` satisfy these constraints. In such cases, `pivotPartition` attempts to distribute equivalent elements fairly to the left and right of k such that k stays close to r.length / 2.
  Parameters:

  less | The predicate used for comparison, modeled as a strict weak ordering (irreflexive, antisymmetric, transitive, and implying a transitive equivalence)
  Range `r` | The range being partitioned
  size_t `pivot` | The index of the pivot for partitioning, must be less than `r`.length or 0 if `r`.length is 0

  Returns:
  The new position of the pivot
  See Also:
  Engineering of a Quicksort Partitioning Algorithm, D. Abhyankar, Journal of Global Research in Computer Science, February 2011. ACCU 2016 Keynote, Andrei Alexandrescu.
  Examples:

      int[] a = [5, 3, 2, 6, 4, 1, 3, 7];
      size_t pivot = pivotPartition(a, a.length / 2);
      import std.algorithm.searching : all;
      assert(a[0 .. pivot].all!(x => x <= a[pivot]));
      assert(a[pivot .. $].all!(x => x >= a[pivot]));

bool `isPartitioned`(alias pred, Range)(Range `r`)
if (isForwardRange!Range);
  Parameters:

  pred | The predicate that the range should be partitioned by.
  Range `r` | The range to check.

  Returns:
  true if `r` is partitioned according to predicate pred.
  Examples:

      int[] r = [ 1, 3, 5, 7, 8, 2, 4, ];
      assert(isPartitioned!"a & 1"(r));

auto `partition3`(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, E)(Range `r`, E `pivot`)
if (ss == SwapStrategy.unstable && isRandomAccessRange!Range && hasSwappableElements!Range && hasLength!Range && hasSlicing!Range && is(typeof(binaryFun!less(`r`.front, `pivot`)) == bool) && is(typeof(binaryFun!less(`pivot`, `r`.front)) == bool) && is(typeof(binaryFun!less(`r`.front, `r`.front)) == bool));
  Rearranges elements in `r` in three adjacent ranges and returns them.
  The first and leftmost range only contains elements in `r` less than `pivot`. The second and middle range only contains elements in `r` that are equal to `pivot`. Finally, the third and rightmost range only contains elements in `r` that are greater than `pivot`. The less-than test is defined by the binary function less.
  Parameters:

  less | The predicate to use for the rearrangement.
  ss | The swapping strategy to use.
  Range `r` | The random-access range to rearrange.
  E `pivot` | The pivot element.

  Returns:
  A std.typecons.Tuple of the three resulting ranges. These ranges are slices of the original range.
  Bugs:
  stable `partition3` has not been implemented yet.
  Examples:

      auto a = [ 8, 3, 4, 1, 4, 7, 4 ];
      auto pieces = partition3(a, 4);
      writeln(pieces[0]); // [1, 3]
      writeln(pieces[1]); // [4, 4, 4]
      writeln(pieces[2]); // [8, 7]

SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b)) `makeIndex`(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range `r`, RangeIndex `index`)
if (isForwardRange!Range && isRandomAccessRange!RangeIndex && is(ElementType!RangeIndex : ElementType!Range*) && hasAssignableElements!RangeIndex);
void `makeIndex`(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range `r`, RangeIndex `index`)
if (isRandomAccessRange!Range && !isInfinite!Range && isRandomAccessRange!RangeIndex && !isInfinite!RangeIndex && isIntegral!(ElementType!RangeIndex) && hasAssignableElements!RangeIndex);
  Computes an index for `r` based on the comparison less.
  The index is a sorted array of pointers or indices into the original range. This technique is similar to sorting, but it is more flexible because (1) it allows "sorting" of immutable collections, (2) allows binary search even if the original collection does not offer random access, (3) allows multiple indexes, each on a different predicate, and (4) may be faster when dealing with large objects. However, using an index may also be slower under certain circumstances due to the extra indirection, and is always larger than a sorting-based solution because it needs space for the index in addition to the original collection. The complexity is the same as sort's.
  The first overload of `makeIndex` writes to a range containing pointers, and the second writes to a range containing offsets. The first overload requires Range to be a forward range, and the latter requires it to be a random-access range.
  `makeIndex` overwrites its second argument with the result, but never reallocates it.
  Parameters:

  less | The comparison to use.
  ss | The swapping strategy.
  Range `r` | The range to index.
  RangeIndex `index` | The resulting index.

  Returns:
  The pointer-based version returns a SortedRange wrapper over index, of type SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b)) thus reflecting the ordering of the index. The index-based version returns void because the ordering relation involves not only `index` but also `r`.
  Throws:
  If the second argument's length is less than that of the range indexed, an exception is thrown.
  Examples:

      immutable(int[]) arr = [ 2, 3, 1, 5, 0 ];
      // index using pointers
      auto index1 = new immutable(int)*[arr.length];
      makeIndex!("a < b")(arr, index1);
      assert(isSorted!("*a < *b")(index1));
      // index using offsets
      auto index2 = new size_t[arr.length];
      makeIndex!("a < b")(arr, index2);
      assert(isSorted!
          ((size_t a, size_t b){ return arr[a] < arr[b];})
          (index2));

Merge!(less, Rs) `merge`(alias less = "a < b", Rs...)(Rs `rs`)
if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) && !is(CommonType!(staticMap!(ElementType, Rs)) == void));
  Merge multiple sorted ranges `rs` with less-than predicate function pred into one single sorted output range containing the sorted union of the elements of inputs.
  Duplicates are not eliminated, meaning that the total number of elements in the output is the sum of all elements in the ranges passed to it; the length member is offered if all inputs also have length. The element types of all the inputs must have a common type CommonType.
  Parameters:

  less | Predicate the given ranges are sorted by.
  Rs `rs` | The ranges to compute the union for.

  Returns:
  A range containing the union of the given ranges.

  Details All of its inputs are assumed to be sorted. This can mean that inputs are instances of std.range.SortedRange. Use the result of std.algorithm.sorting.sort, or std.range.assumeSorted to merge ranges known to be sorted (show in the example below). Note that there is currently no way of ensuring that two or more instances of std.range.SortedRange are sorted using a specific comparison function pred. Therefore no checking is done here to assure that all inputs `rs` are instances of std.range.SortedRange.

  This algorithm is lazy, doing work progressively as elements are pulled off the result.
  Time complexity is proportional to the sum of element counts over all inputs.
  If all inputs have the same element type and offer it by ref, output becomes a range with mutable front (and back where appropriate) that reflects in the original inputs.
  If any of the inputs `rs` is infinite so is the result (empty being always false).
  See Also:
  std.algorithm.setops.multiwayMerge for an analogous function that merges a dynamic number of ranges.
  Examples:

      import std.algorithm.comparison : equal;
      import std.range : retro;

      int[] a = [1, 3, 5];
      int[] b = [2, 3, 4];

      assert(a.merge(b).equal([1, 2, 3, 3, 4, 5]));
      assert(a.merge(b).retro.equal([5, 4, 3, 3, 2, 1]));

  Examples:
  test bi-directional access and common type

      import std.algorithm.comparison : equal;
      import std.range : retro;
      import std.traits : CommonType;

      alias S = short;
      alias I = int;
      alias D = double;

      S[] a = [1, 2, 3];
      I[] b = [50, 60];
      D[] c = [10, 20, 30, 40];

      auto m = merge(a, b, c);

      static assert(is(typeof(m.front) == CommonType!(S, I, D)));

      assert(equal(m, [1, 2, 3, 10, 20, 30, 40, 50, 60]));
      assert(equal(m.retro, [60, 50, 40, 30, 20, 10, 3, 2, 1]));

      m.popFront();
      assert(equal(m, [2, 3, 10, 20, 30, 40, 50, 60]));
      m.popBack();
      assert(equal(m, [2, 3, 10, 20, 30, 40, 50]));
      m.popFront();
      assert(equal(m, [3, 10, 20, 30, 40, 50]));
      m.popBack();
      assert(equal(m, [3, 10, 20, 30, 40]));
      m.popFront();
      assert(equal(m, [10, 20, 30, 40]));
      m.popBack();
      assert(equal(m, [10, 20, 30]));
      m.popFront();
      assert(equal(m, [20, 30]));
      m.popBack();
      assert(equal(m, [20]));
      m.popFront();
      assert(m.empty);

template `multiSort`(less...)
  Sorts a range by multiple keys.
  The call multiSort!("a.id < b.id", "a.date > b.date")(r) sorts the range r by id ascending, and sorts elements that have the same id by date descending. Such a call is equivalent to sort!"a.id != b.id ? a.id < b.id : a.date > b.date"(r), but `multiSort` is faster because it does fewer comparisons (in addition to being more convenient).
  Returns:
  The initial range wrapped as a SortedRange with its predicates converted to an equivalent single predicate.
  Examples:

      import std.algorithm.mutation : SwapStrategy;
      static struct Point { int x, y; }
      auto pts1 = [ Point(0, 0), Point(5, 5), Point(0, 1), Point(0, 2) ];
      auto pts2 = [ Point(0, 0), Point(0, 1), Point(0, 2), Point(5, 5) ];
      multiSort!("a.x < b.x", "a.y < b.y", SwapStrategy.unstable)(pts1);
      writeln(pts1); // pts2

SortedRange!(Range, less) `sort`(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range `r`)
if ((ss == SwapStrategy.unstable && (hasSwappableElements!Range || hasAssignableElements!Range) || ss != SwapStrategy.unstable && hasAssignableElements!Range) && isRandomAccessRange!Range && hasSlicing!Range && hasLength!Range);
  Sorts a random-access range according to the predicate less.
  Performs Ο(r.length * log(r.length)) evaluations of less. If less involves expensive computations on the sort key, it may be worthwhile to use schwartzSort instead.
  Stable sorting requires hasAssignableElements!Range to be true.
  `sort` returns a std.range.SortedRange over the original range, allowing functions that can take advantage of sorted data to know that the range is sorted and adjust accordingly. The std.range.SortedRange is a wrapper around the original range, so both it and the original range are sorted. Other functions can't know that the original range has been sorted, but they can know that std.range.SortedRange has been sorted.

  Preconditions The predicate is expected to satisfy certain rules in order for `sort` to behave as expected - otherwise, the program may fail on certain inputs (but not others) when not compiled in release mode, due to the cursory assumeSorted check. Specifically, `sort` expects less(a,b) && less(b,c) to imply less(a,c) (transitivity), and, conversely, !less(a,b) && !less(b,c) to imply !less(a,c). Note that the default predicate ("a < b") does not always satisfy these conditions for floating point types, because the expression will always be false when either a or b is NaN. Use std.math.cmp instead.

  Parameters:

  less | The predicate to sort by.
  ss | The swapping strategy to use.
  Range `r` | The range to sort.

  Returns:
  The initial range wrapped as a SortedRange with the predicate binaryFun!less.

  Algorithms Introsort is used for unstable sorting and Timsort is used for stable sorting. Each algorithm has benefits beyond stability. Introsort is generally faster but Timsort may achieve greater speeds on data with low entropy or if predicate calls are expensive. Introsort performs no allocations whereas Timsort will perform one or more allocations per call. Both algorithms have Ο(n log n) worst-case time complexity.

  See Also:
  std.range.assumeSorted
  std.range.SortedRange
  std.algorithm.mutation.SwapStrategy
  std.functional.binaryFun
  Examples:

      int[] array = [ 1, 2, 3, 4 ];

      // sort in descending order
      array.sort!("a > b");
      writeln(array); // [4, 3, 2, 1]

      // sort in ascending order
      array.sort();
      writeln(array); // [1, 2, 3, 4]

      // sort with reusable comparator and chain
      alias myComp = (x, y) => x > y;
      writeln(array.sort!(myComp).release); // [4, 3, 2, 1]

  Examples:

      // Showcase stable sorting
      import std.algorithm.mutation : SwapStrategy;
      string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ];
      sort!("toUpper(a) < toUpper(b)", SwapStrategy.stable)(words);
      writeln(words); // ["a", "aBc", "abc", "ABC", "b", "c"]

  Examples:

      // Sorting floating-point numbers in presence of NaN
      double[] numbers = [-0.0, 3.0, -2.0, double.nan, 0.0, -double.nan];

      import std.algorithm.comparison : equal;
      import std.math.operations : cmp;
      import std.math.traits : isIdentical;

      sort!((a, b) => cmp(a, b) < 0)(numbers);

      double[] sorted = [-double.nan, -2.0, -0.0, 0.0, 3.0, double.nan];
      assert(numbers.equal!isIdentical(sorted));

SortedRange!(R, (a, b) => binaryFun!less(unaryFun!transform(a), unaryFun!transform(b))) `schwartzSort`(alias transform, alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, R)(R `r`)
if (isRandomAccessRange!R && hasLength!R && hasSwappableElements!R && !is(typeof(binaryFun!less) == SwapStrategy));
auto `schwartzSort`(alias transform, SwapStrategy ss, R)(R `r`)
if (isRandomAccessRange!R && hasLength!R && hasSwappableElements!R);
  Alternative sorting method that should be used when comparing keys involves an expensive computation.
  Instead of using less(a, b) for comparing elements, `schwartzSort` uses less(transform(a), transform(b)). The values of the transform function are precomputed in a temporary array, thus saving on repeatedly computing it. Conversely, if the cost of transform is small compared to the cost of allocating and filling the precomputed array, sort may be faster and therefore preferable.
  This approach to sorting is akin to the Schwartzian transform, also known as the decorate-sort-undecorate pattern in Python and Lisp. The complexity is the same as that of the corresponding sort, but `schwartzSort` evaluates transform only `r`.length times (less than half when compared to regular sorting). The usage can be best illustrated with an example.

  Example

      uint hashFun(string) { ... expensive computation ... }
      string[] array = ...;
      // Sort strings by hash, slow
      sort!((a, b) => hashFun(a) < hashFun(b))(array);
      // Sort strings by hash, fast (only computes arr.length hashes):
      schwartzSort!(hashFun, "a < b")(array);

  The `schwartzSort` function might require less temporary data and be faster than the Perl idiom or the decorate-sort-undecorate idiom present in Python and Lisp. This is because sorting is done in-place and only minimal extra data (one array of transformed elements) is created.
  To check whether an array was sorted and benefit of the speedup of Schwartz sorting, a function schwartzIsSorted is not provided because the effect can be achieved by calling isSorted!less(map!transform(r)).
  Parameters:

  transform | The transformation to apply. Either a unary function (unaryFun!transform(element)), or a binary function (binaryFun!transform(element, index)).
  less | The predicate to sort the transformed elements by.
  ss | The swapping strategy to use.
  R `r` | The range to sort.

  Returns:
  The initial range wrapped as a SortedRange with the predicate (a, b) => binaryFun!less(transform(a), transform(b)).
  Examples:

      import std.algorithm.iteration : map;
      import std.numeric : entropy;

      auto lowEnt = [ 1.0, 0, 0 ],
           midEnt = [ 0.1, 0.1, 0.8 ],
          highEnt = [ 0.31, 0.29, 0.4 ];
      auto arr = new double[][3];
      arr[0] = midEnt;
      arr[1] = lowEnt;
      arr[2] = highEnt;

      schwartzSort!(entropy, "a > b")(arr);

      writeln(arr[0]); // highEnt
      writeln(arr[1]); // midEnt
      writeln(arr[2]); // lowEnt
      assert(isSorted!("a > b")(map!(entropy)(arr)));

void `partialSort`(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range `r`, size_t `n`)
if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range);
  Reorders the random-access range `r` such that the range `r`[0 .. mid] is the same as if the entire `r` were sorted, and leaves the range `r`[mid .. `r`.length] in no particular order.
  Performs Ο(r.length * log(mid)) evaluations of pred. The implementation simply calls topN!(less, ss)(`r`, `n`) and then sort!(less, ss)(r[0 .. n]).
  Parameters:

  less | The predicate to sort by.
  ss | The swapping strategy to use.
  Range `r` | The random-access range to reorder.
  size_t `n` | The length of the initial segment of `r` to sort.

  Examples:

      int[] a = [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ];
      partialSort(a, 5);
      writeln(a[0 .. 5]); // [0, 1, 2, 3, 4]

void `partialSort`(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range1, Range2)(Range1 `r1`, Range2 `r2`)
if (isRandomAccessRange!Range1 && hasLength!Range1 && isInputRange!Range2 && is(ElementType!Range1 == ElementType!Range2) && hasLvalueElements!Range1 && hasLvalueElements!Range2);
  Stores the smallest elements of the two ranges in the left-hand range in sorted order.
  Parameters:

  less | The predicate to sort by.
  ss | The swapping strategy to use.
  Range1 `r1` | The first range.
  Range2 `r2` | The second range.

  Examples:

      int[] a = [5, 7, 2, 6, 7];
      int[] b = [2, 1, 5, 6, 7, 3, 0];

      partialSort(a, b);
      writeln(a); // [0, 1, 2, 2, 3]

auto `topN`(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range `r`, size_t `nth`)
if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range && hasAssignableElements!Range);
  Reorders the range `r` using swap such that `r`[`nth`] refers to the element that would fall there if the range were fully sorted.
  It is akin to Quickselect, and partitions `r` such that all elements e1 from `r`[0] to `r`[`nth`] satisfy !less(`r`[`nth`], e1), and all elements e2 from `r`[`nth`] to `r`[`r`.length] satisfy !less(e2, `r`[`nth`]). Effectively, it finds the `nth` + 1 smallest (according to less) elements in `r`. Performs an expected Ο(r.length) (if unstable) or Ο(r.length * log(r.length)) (if stable) evaluations of less and swap.
  If n >= `r`.length, the algorithm has no effect and returns `r`[0 .. `r`.length].
  Parameters:

  less | The predicate to sort by.
  ss | The swapping strategy to use.
  Range `r` | The random-access range to reorder.
  size_t `nth` | The index of the element that should be in sorted position after the function is done.

  Returns:
  a slice from `r`[0] to `r`[`nth`], excluding `r`[`nth`] itself.
  See Also:
  topNIndex,
  Bugs:
  Stable topN has not been implemented yet.
  Examples:

      int[] v = [ 25, 7, 9, 2, 0, 5, 21 ];
      topN!"a < b"(v, 100);
      writeln(v); // [25, 7, 9, 2, 0, 5, 21]
      auto n = 4;
      topN!((a, b) => a < b)(v, n);
      writeln(v[n]); // 9

auto `topN`(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range1, Range2)(Range1 `r1`, Range2 `r2`)
if (isRandomAccessRange!Range1 && hasLength!Range1 && isInputRange!Range2 && is(ElementType!Range1 == ElementType!Range2) && hasLvalueElements!Range1 && hasLvalueElements!Range2);
  Stores the smallest elements of the two ranges in the left-hand range.
  Parameters:

  less | The predicate to sort by.
  ss | The swapping strategy to use.
  Range1 `r1` | The first range.
  Range2 `r2` | The second range.

  Examples:

      int[] a = [ 5, 7, 2, 6, 7 ];
      int[] b = [ 2, 1, 5, 6, 7, 3, 0 ];
      topN(a, b);
      sort(a);
      writeln(a); // [0, 1, 2, 2, 3]

TRange `topNCopy`(alias less = "a < b", SRange, TRange)(SRange `source`, TRange `target`, SortOutput `sorted` = No.sortOutput)
if (isInputRange!SRange && isRandomAccessRange!TRange && hasLength!TRange && hasSlicing!TRange);
  Copies the top n elements of the input range `source` into the random-access range `target`, where n = `target`.length.
  Elements of `source` are not touched. If sorted is true, the target is sorted. Otherwise, the target respects the heap property.
  Parameters:

  less | The predicate to sort by.
  SRange `source` | The source range.
  TRange `target` | The target range.
  SortOutput `sorted` | Whether to sort the elements copied into `target`.

  Returns:
  The slice of `target` containing the copied elements.
  Examples:

      import std.typecons : Yes;

      int[] a = [ 10, 16, 2, 3, 1, 5, 0 ];
      int[] b = new int[3];
      topNCopy(a, b, Yes.sortOutput);
      writeln(b); // [0, 1, 2]

void `topNIndex`(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range `r`, RangeIndex `index`, SortOutput `sorted` = No.sortOutput)
if (isRandomAccessRange!Range && isRandomAccessRange!RangeIndex && hasAssignableElements!RangeIndex);
  Given a range of elements, constructs an index of its top n elements (i.e., the first n elements if the range were sorted).
  Similar to topN, except that the range is not modified.
  Parameters:

  less | A binary predicate that defines the ordering of range elements. Defaults to a < b.
  ss | (Not implemented yet.) Specify the swapping strategy.
  Range `r` | A random-access range of elements to make an index for.
  RangeIndex `index` | A random-access range with assignable elements to build the index in. The length of this range determines how many top elements to index in `r`. This index range can either have integral elements, in which case the constructed index will consist of zero-based numerical indices into `r`; or it can have pointers to the element type of `r`, in which case the constructed index will be pointers to the top elements in `r`.
  SortOutput `sorted` | Determines whether to sort the index by the elements they refer to.

  See Also:
  topN, topNCopy.
  Bugs:
  The swapping strategy parameter is not implemented yet; currently it is ignored.
  Examples:

      import std.typecons : Yes;

      // Construct index to top 3 elements using numerical indices:
      int[] a = [ 10, 2, 7, 5, 8, 1 ];
      int[] index = new int[3];
      topNIndex(a, index, Yes.sortOutput);
      assert(index == [5, 1, 3]); // because a[5]==1, a[1]==2, a[3]==5

      // Construct index to top 3 elements using pointer indices:
      int*[] ptrIndex = new int*[3];
      topNIndex(a, ptrIndex, Yes.sortOutput);
      writeln(ptrIndex); // [&a[5], &a[1], &a[3]]

bool `nextPermutation`(alias less = "a < b", BidirectionalRange)(BidirectionalRange `range`)
if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange);
  Permutes `range` in-place to the next lexicographically greater permutation.
  The predicate less defines the lexicographical ordering to be used on the range.
  If the range is currently the lexicographically greatest permutation, it is permuted back to the least permutation and false is returned. Otherwise, true is returned. One can thus generate all permutations of a range by sorting it according to less, which produces the lexicographically least permutation, and then calling nextPermutation until it returns false. This is guaranteed to generate all distinct permutations of the range exactly once. If there are N elements in the range and all of them are unique, then N! permutations will be generated. Otherwise, if there are some duplicated elements, fewer permutations will be produced.

      // Enumerate all permutations
      int[] a = [1,2,3,4,5];
      do
      {
          // use the current permutation and
          // proceed to the next permutation of the array.
      } while (nextPermutation(a));

  Parameters:

  less | The ordering to be used to determine lexicographical ordering of the permutations.
  BidirectionalRange `range` | The range to permute.

  Returns:
  false if the range was lexicographically the greatest, in which case the range is reversed back to the lexicographically smallest permutation; otherwise returns true.
  See Also:
  std.algorithm.iteration.permutations.
  Examples:

      // Step through all permutations of a sorted array in lexicographic order
      int[] a = [1,2,3];
      writeln(nextPermutation(a)); // true
      writeln(a); // [1, 3, 2]
      writeln(nextPermutation(a)); // true
      writeln(a); // [2, 1, 3]
      writeln(nextPermutation(a)); // true
      writeln(a); // [2, 3, 1]
      writeln(nextPermutation(a)); // true
      writeln(a); // [3, 1, 2]
      writeln(nextPermutation(a)); // true
      writeln(a); // [3, 2, 1]
      writeln(nextPermutation(a)); // false
      writeln(a); // [1, 2, 3]

  Examples:

      // Step through permutations of an array containing duplicate elements:
      int[] a = [1,1,2];
      writeln(nextPermutation(a)); // true
      writeln(a); // [1, 2, 1]
      writeln(nextPermutation(a)); // true
      writeln(a); // [2, 1, 1]
      writeln(nextPermutation(a)); // false
      writeln(a); // [1, 1, 2]

bool `nextEvenPermutation`(alias less = "a < b", BidirectionalRange)(BidirectionalRange `range`)
if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange);
  Permutes `range` in-place to the next lexicographically greater even permutation.
  The predicate less defines the lexicographical ordering to be used on the range.
  An even permutation is one which is produced by swapping an even number of pairs of elements in the original range. The set of even permutations is distinct from the set of all permutations only when there are no duplicate elements in the range. If the range has N unique elements, then there are exactly N!/2 even permutations.
  If the range is already the lexicographically greatest even permutation, it is permuted back to the least even permutation and false is returned. Otherwise, true is returned, and the range is modified in-place to be the lexicographically next even permutation.
  One can thus generate the even permutations of a range with unique elements by starting with the lexicographically smallest permutation, and repeatedly calling nextEvenPermutation until it returns false.

      // Enumerate even permutations
      int[] a = [1,2,3,4,5];
      do
      {
          // use the current permutation and
          // proceed to the next even permutation of the array.
      } while (nextEvenPermutation(a));

  One can also generate the odd permutations of a range by noting that permutations obey the rule that even + even = even, and odd + even = odd. Thus, by swapping the last two elements of a lexicographically least range, it is turned into the first odd permutation. Then calling nextEvenPermutation on this first odd permutation will generate the next even permutation relative to this odd permutation, which is actually the next odd permutation of the original range. Thus, by repeatedly calling nextEvenPermutation until it returns false, one enumerates the odd permutations of the original range.

      // Enumerate odd permutations
      int[] a = [1,2,3,4,5];
      swap(a[$-2], a[$-1]);    // a is now the first odd permutation of [1,2,3,4,5]
      do
      {
          // use the current permutation and
          // proceed to the next odd permutation of the original array
          // (which is an even permutation of the first odd permutation).
      } while (nextEvenPermutation(a));

  Warning Since even permutations are only distinct from all permutations when the range elements are unique, this function assumes that there are no duplicate elements under the specified ordering. If this is not true, some permutations may fail to be generated. When the range has non-unique elements, you should use nextPermutation instead.

  Parameters:

  less | The ordering to be used to determine lexicographical ordering of the permutations.
  BidirectionalRange `range` | The range to permute.

  Returns:
  false if the range was lexicographically the greatest, in which case the range is reversed back to the lexicographically smallest permutation; otherwise returns true.
  Examples:

      // Step through even permutations of a sorted array in lexicographic order
      int[] a = [1,2,3];
      writeln(nextEvenPermutation(a)); // true
      writeln(a); // [2, 3, 1]
      writeln(nextEvenPermutation(a)); // true
      writeln(a); // [3, 1, 2]
      writeln(nextEvenPermutation(a)); // false
      writeln(a); // [1, 2, 3]

  Examples:
  Even permutations are useful for generating coordinates of certain geometric shapes. Here's a non-trivial example:

      import std.math.algebraic : sqrt;

      // Print the 60 vertices of a uniform truncated icosahedron (soccer ball)
      enum real Phi = (1.0 + sqrt(5.0)) / 2.0;    // Golden ratio
      real[][] seeds = [
          [0.0, 1.0, 3.0*Phi],
          [1.0, 2.0+Phi, 2.0*Phi],
          [Phi, 2.0, Phi^^3]
      ];
      size_t n;
      foreach (seed; seeds)
      {
          // Loop over even permutations of each seed
          do
          {
              // Loop over all sign changes of each permutation
              size_t i;
              do
              {
                  // Generate all possible sign changes
                  for (i=0; i < seed.length; i++)
                  {
                      if (seed[i] != 0.0)
                      {
                          seed[i] = -seed[i];
                          if (seed[i] < 0.0)
                              break;
                      }
                  }
                  n++;
              } while (i < seed.length);
          } while (nextEvenPermutation(seed));
      }
      writeln(n); // 60

ref Range `nthPermutation`(Range)(auto ref Range `range`, const ulong `perm`)
if (isRandomAccessRange!Range && hasLength!Range);
  Permutes `range` into the `perm` permutation.
  The algorithm has a constant runtime complexity with respect to the number of permutations created. Due to the number of unique values of ulong only the first 21 elements of `range` can be permuted. The rest of the range will therefore not be permuted. This algorithm uses the Lehmer Code.
  The algorithm works as follows:

          auto pem = [4,0,4,1,0,0,0]; // permutation 2982 in factorial
          auto src = [0,1,2,3,4,5,6]; // the range to permutate

          auto i = 0;                    // range index
          // range index iterates pem and src in sync
          // pem[i] + i is used as index into src
          // first src[pem[i] + i] is stored in t
          auto t = 4;                    // tmp value
          src = [0,1,2,3,n,5,6];

          // then the values between i and pem[i] + i are moved one
          // to the right
          src = [n,0,1,2,3,5,6];
          // at last t is inserted into position i
          src = [4,0,1,2,3,5,6];
          // finally i is incremented
          ++i;

          // this process is repeated while i < pem.length

          t = 0;
          src = [4,n,1,2,3,5,6];
          src = [4,0,1,2,3,5,6];
          ++i;
          t = 6;
          src = [4,0,1,2,3,5,n];
          src = [4,0,n,1,2,3,5];
          src = [4,0,6,1,2,3,5];

  Returns:
  The permuted range.
  Parameters:

  Range `range` | The Range to permute. The original ordering will be lost.
  ulong `perm` | The permutation to permutate `range` to.

  Examples:

      auto src = [0, 1, 2, 3, 4, 5, 6];
      auto rslt = [4, 0, 6, 2, 1, 3, 5];

      src = nthPermutation(src, 2982);
      writeln(src); // rslt

bool `nthPermutationImpl`(Range)(auto ref Range `range`, ulong `perm`)
if (isRandomAccessRange!Range && hasLength!Range);
  Returns:
  true in case the permutation worked, false in case `perm` had more digits in the factorial number system than range had elements. This case must not occur as this would lead to out of range accesses.
  Examples:

      auto src = [0, 1, 2, 3, 4, 5, 6];
      auto rslt = [4, 0, 6, 2, 1, 3, 5];

      bool worked = nthPermutationImpl(src, 2982);
      assert(worked);
      writeln(src); // rslt

Copyright © 1999-2023 by the D Language Foundation | Page generated by Ddoc on Wed Feb 1 17:27:32 2023