# Module std_dev::percentile

source · ## Expand description

Percentile / median calculations.

`O(n log n)`

`naive_percentile`

(simple to understand)- probabilistic
`O(n)`

`percentile`

(recommended, fastest, and also quite simple to understand) - deterministic
`O(n)`

`median_of_medians`

(harder to understand, probably slower than the probabilistic version. However guarantees linear time, so useful in critical applications.)

You should probably use `percentile_rand`

.

The linear time algoritms are implementations following this blogpost.

## Modules

- Operations on
`crate::Cluster`

s.

## Structs

- A simplified fraction. This is used to get a percentile from any function in this module.
- Get the k-th largest value. Implements
`OrderedListIndex`

. - Get the k-th smallest value. Implements
`OrderedListIndex`

.

## Enums

- The result of a percentile (e.g. median) lookup.

## Traits

- Resolves the mean function to return a concrete value. Accessible through
`MeanValue::resolve`

.

## Functions

- Convenience function for
`percentile`

with the 50% mark as the target and`pivot_fn::rand`

(if the`percentile-rand`

feature is enabled, else`pivot_fn::middle`

). - Same result as
`percentile_rand`

but in deterministic linear time. But probabilistically way slower. - Same as
`median_of_medians`

but with a custom comparator function. - Percentile by sorting.
- Same as
`naive_percentile`

but with a custom comparator function. - quickselect algorithm
- Same as
`percentile`

but with a custom comparator function. - Get the value at
`target`

in`values`

. Uses the best method available (`percentile_rand`

if feature`percentile-rand`

is enabled, else`pivot_fn::middle`

) - Same as
`percentile_default_pivot`

but with a custom comparator function. - percentile_rand
`percentile-rand`

Convenience function for`percentile`

with`pivot_fn::rand`

. - Moves items in the slice and splits it so the first returned slice contains all elements where
`predicate`

is true. The second contains all other.