Function std.algorithm.sorting.schwartzSort
Sorts a range using an algorithm akin to the Schwartzian transform, also
known as the decorate-sort-undecorate pattern in Python and Lisp.
This function is helpful when the sort comparison includes
an expensive computation. The complexity is the same as that of the
corresponding sortschwartzSorttransform only r.length times (less than half when compared to
regular sorting). The usage can be best illustrated with an example.
Prototype
SortedRange!(R,(a,b)=>binaryFun!less(unaryFun!transform(a),unaryFun!transform(b))) schwartzSort(alias transform, alias less, std.algorithm.mutation.SwapStrategy ss, R)( R r ) if (isRandomAccessRange!R && hasLength!R);
Examples
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 schwartzSortsort-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
| Name | Description |
|---|---|
| transform | The transformation to apply. |
| less | The predicate to sort by. |
| ss | The swapping strategy to use. |
| r | The range to sort. |
Returns
The initial range wrapped as a SortedRange with the
predicate (a, b) => binaryFun!less(transform(a),
transform(b)).