The OpenD Programming Language

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.

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 O(r.length) (if unstable) or O(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].

  1. auto topN(Range r, size_t nth)
    topN
    (
    alias less = "a < b"
    Range
    )
    (
    Range r
    ,
    size_t nth
    )
    if ()
  2. auto topN(Range1 r1, Range2 r2)

Parameters

less

The predicate to sort by.

ss

The swapping strategy to use.

r Range

The random-access range to reorder.

nth size_t

The index of the element that should be in sorted position after the function is done.

Return Value

Type: auto

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

Bugs

Stable topN has not been implemented yet.

Examples

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

See Also

Meta