Sorting v0.1.0

Sort<T>

pub func Sort<T>(items: var T[..])

Puts items into non-decreasing order. items is borrowed mutably and rewritten. Fewer than two elements are already sorted, so the data pointer is never read in that case and an empty view is not a special case. Requires < on the element type, as a strict weak ordering. Equal elements may be reordered: this is not stable. Cannot fail. Makes O(n log n) comparisons for every input, uses O(1) storage beyond the sequence, and recurses O(log n) deep.

Source

Type parameters

Parameters

SortDescending<T>

pub func SortDescending<T>(items: var T[..])

Puts items into non-increasing order. items is borrowed mutably and rewritten. An ascending sort followed by a reversal, rather than a mirrored copy of every helper below: threading a direction flag through the partition and both fallbacks would cost a branch in the innermost comparison, and duplicating the helpers would double the amount of subtle index arithmetic to maintain, all for one extra linear pass. Sorting is unstable in either direction, so reversing costs nothing in ordering either. Requires < on the element type. Equal elements may be reordered. Cannot fail. Makes O(n log n) comparisons and uses O(1) storage beyond the sequence.

Source

Type parameters

Parameters

NthElement<T>

pub func NthElement<T>(items: var T[..], n: uint) -> bool

Puts the element that belongs at n in a fully sorted items at n, and partitions around it. items is borrowed mutably and rewritten; n is read by value. Afterwards everything before n is at most the element at n and everything after is at least it. Neither side is ordered any further, which is the whole point: this is what to reach for when only one order statistic is wanted — a median, a percentile — because it is linear on average where a full sort is not. Reports false, changing nothing, when n is not an index into items. That is the only way this fails. Quickselect over the same partition Sort uses, but iterative: only one side of a partition can contain n, so there is nothing to recurse into and the stack stays flat. The same depth budget bounds the worst case at O(n log n), against O(n) on average. Requires < on the element type. Equal elements may be reordered.

Source

Type parameters

Parameters

Returns: whether n was a usable index

PartialSort<T>

pub func PartialSort<T>(
    items: var T[..],
    count: uint
) -> bool

Puts the count smallest elements of items in order at its front. items is borrowed mutably and rewritten; count is read by value. The first count positions hold the smallest elements in non-decreasing order, and the rest hold everything else in no particular order. Reports false, changing nothing, when count is larger than the length. A count of zero succeeds and does nothing. A max-heap over the first count elements, which each later element is compared against and displaces only if it is smaller: O(n log count) comparisons, against the O(n log n) a full sort would cost. That is worth having when count is much smaller than the length and not otherwise. Requires < on the element type. Equal elements may be reordered.

Source

Type parameters

Parameters

Returns: whether count was a usable length

InsertionSortRange<T>

pub func InsertionSortRange<T>(
    data: *var T,
    low: uint,
    high: uint
)

Provides the public InsertionSortRange operation.

Source

Type parameters

Parameters

HeapSortRange<T>

pub func HeapSortRange<T>(
    data: *var T,
    low: uint,
    high: uint
)

Provides the public HeapSortRange operation.

Source

Type parameters

Parameters

SortBy<T>

pub func SortBy<T>(
    items: var T[..],
    compare: func(T, T) -> Ordering
)

Puts items into the order compare describes, smallest first. items is borrowed mutably and rewritten; compare is called O(n log n) times and must be a strict weak ordering, exactly as < must be. Equivalence is derived from it alone, so the element type need not define any operator at all. Cannot fail. Makes O(n log n) comparisons for every input, uses O(1) storage beyond the sequence, and recurses O(log n) deep. Equal elements may be reordered: this is not stable.

Source

Type parameters

Parameters

SortDescendingBy<T>

pub func SortDescendingBy<T>(
    items: var T[..],
    compare: func(T, T) -> Ordering
)

Puts items into the reverse of the order compare describes. items is borrowed mutably and rewritten; compare is called O(n log n) times. An ascending sort followed by a reversal, for the same reason SortDescending is. Cannot fail. Makes O(n log n) comparisons and uses O(1) storage beyond the sequence. Equal elements may be reordered.

Source

Type parameters

Parameters

NthElementBy<T>

pub func NthElementBy<T>(
    items: var T[..],
    n: uint,
    compare: func(T, T) -> Ordering
) -> bool

Puts the element that belongs at n under compare at n, and partitions around it. items is borrowed mutably and rewritten; n is read by value; compare must be a strict weak ordering. Exactly NthElement, with the order supplied rather than taken from the element type. Reports false, changing nothing, when n is not an index into items. O(n) comparisons on average and O(n log n) at worst. Equivalent elements may be reordered.

Source

Type parameters

Parameters

Returns: whether n was a usable index

PartialSortBy<T>

pub func PartialSortBy<T>(
    items: var T[..],
    count: uint,
    compare: func(T, T) -> Ordering
) -> bool

Puts the count smallest elements of items under compare in order at its front. items is borrowed mutably and rewritten; count is read by value; compare must be a strict weak ordering. Exactly PartialSort, with the order supplied rather than taken from the element type. Reports false, changing nothing, when count is larger than the length. O(n log count) comparisons. Equivalent elements may be reordered.

Source

Type parameters

Parameters

Returns: whether count was a usable length

RequiredScratch

pub func RequiredScratch(length: uint) -> uint

How much scratch storage a stable sort of length elements needs. length is read by value. The answer is length itself: a merge writes its output somewhere other than either of the two runs it reads, and the last merge reads the whole sequence. Written as a function rather than left to the reader so that a caller sizing a buffer does not have to know that, and so that it stays right if it ever stops being the whole length. Cannot fail. Runs in constant time and allocates nothing.

Source

Parameters

Returns: how many elements of working storage a stable sort of that length needs

StableSort<T>

pub func StableSort<T>(
    items: var T[..],
    scratch: var T[..]
) -> bool

Puts items into non-decreasing order, leaving equal elements in the order they were in. items is borrowed mutably and rewritten; scratch is borrowed mutably and used as working storage, and what it holds afterwards is unspecified. Fewer than two elements are already sorted and need no scratch at all. Reports false, changing nothing, when scratch is shorter than RequiredScratch(items.length). That is the only way this fails. Requires < on the element type, as a strict weak ordering. Makes O(n log n) comparisons and moves for every input — there is no bad case — and allocates nothing.

Source

Type parameters

Parameters

Returns: whether scratch was large enough; the sequence is untouched when it was not

StableSortBy<T>

pub func StableSortBy<T>(
    items: var T[..],
    scratch: var T[..],
    compare: func(T, T) -> Ordering
) -> bool

Puts items into the order compare describes, leaving equivalent elements in the order they were in. items is borrowed mutably and rewritten; scratch is borrowed mutably and used as working storage, and what it holds afterwards is unspecified. compare is called O(n log n) times and must be a strict weak ordering. Reports false, changing nothing, when scratch is shorter than RequiredScratch(items.length). Makes O(n log n) comparisons and moves for every input, and allocates nothing.

Source

Type parameters

Parameters

Returns: whether scratch was large enough; the sequence is untouched when it was not