View source code
Display the source code in std/algorithm/sorting.d from which this
page was generated on github.
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
local clone.
std.algorithm.sorting.topN - multiple declarations
Function topN
Reorders the range r using swap
such that r[nth] refers to the element that would fall there if the range
were fully sorted.
auto topN(alias less, SwapStrategy ss = SwapStrategy
Range r,
size_t nth
)
if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range && hasAssignableElements!Range);
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 satisfy
!less(e2, r[nth]). Effectively, it finds the nth + 1 smallest
(according to less) elements in r. Performs an expected
Ο(r) (if unstable) or Ο(r)
(if stable) evaluations of less and swap.
If n >= r, the algorithm has no effect and returns
r[0 .. r.
Parameters
| Name | Description |
|---|---|
| less | The predicate to sort by. |
| ss | The swapping strategy to use. |
| r | The random-access range to reorder. |
| nth | The index of the element that should be in sorted position after the function is done. |
Returns
See Also
BUGS
Stable topN has not been implemented yet.
Example
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
Function topN
Stores the smallest elements of the two ranges in the left-hand range.
auto topN(alias less, SwapStrategy ss = SwapStrategy
Range1 r1,
Range2 r2
)
if (isRandomAccessRange!Range1 && hasLength!Range1 && isInputRange!Range2 && is(ElementType!Range1 == ElementType!Range2) && hasLvalueElements!Range1 && hasLvalueElements!Range2);
Parameters
| Name | Description |
|---|---|
| less | The predicate to sort by. |
| ss | The swapping strategy to use. |
| r1 | The first range. |
| r2 | The second range. |
Example
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]
Authors
License
Copyright © 1999-2022 by the D Language Foundation | Page generated by ddox.