Search
View source code
Display the source code in std/algorithm/sorting.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.

# `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.unstable, Range) (   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` 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

NameDescription
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

a slice from `r` to `r[nth]`, excluding `r[nth]` itself.

`topNIndex`,

### 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.unstable, Range1, Range2) (   Range1 r1,   Range2 r2 ) if (isRandomAccessRange!Range1 && hasLength!Range1 && isInputRange!Range2 && is(ElementType!Range1 == ElementType!Range2) && hasLvalueElements!Range1 && hasLvalueElements!Range2); ```

### Parameters

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