Trait ndarray_stats::Sort1dExt
source · [−]pub trait Sort1dExt<A, S> where
S: Data<Elem = A>, {
fn get_from_sorted_mut(&mut self, i: usize) -> A
where
A: Ord + Clone,
S: DataMut;
fn get_many_from_sorted_mut<S2>(
&mut self,
indexes: &ArrayBase<S2, Ix1>
) -> IndexMap<usize, A>
where
A: Ord + Clone,
S: DataMut,
S2: Data<Elem = usize>;
fn partition_mut(&mut self, pivot_index: usize) -> usize
where
A: Ord + Clone,
S: DataMut;
fn __private__(&self, _: PrivateMarker);
}Expand description
Methods for sorting and partitioning 1-D arrays.
Required Methods
Return the element that would occupy the i-th position if
the array were sorted in increasing order.
The array is shuffled in place to retrieve the desired element:
no copy of the array is allocated.
After the shuffling, all elements with an index smaller than i
are smaller than the desired element, while all elements with
an index greater or equal than i are greater than or equal
to the desired element.
No other assumptions should be made on the ordering of the elements after this computation.
Complexity (quickselect):
- average case: O(
n); - worst case: O(
n^2); where n is the number of elements in the array.
Panics if i is greater than or equal to n.
A bulk version of get_from_sorted_mut, optimized to retrieve multiple
indexes at once.
It returns an IndexMap, with indexes as keys and retrieved elements as
values.
The IndexMap is sorted with respect to indexes in increasing order:
this ordering is preserved when you iterate over it (using iter/into_iter).
Panics if any element in indexes is greater than or equal to n,
where n is the length of the array..
Partitions the array in increasing order based on the value initially
located at pivot_index and returns the new index of the value.
The elements are rearranged in such a way that the value initially
located at pivot_index is moved to the position it would be in an
array sorted in increasing order. The return value is the new index of
the value after rearrangement. All elements smaller than the value are
moved to its left and all elements equal or greater than the value are
moved to its right. The ordering of the elements in the two partitions
is undefined.
self is shuffled in place to operate the desired partition:
no copy of the array is allocated.
The method uses Hoare’s partition algorithm.
Complexity: O(n), where n is the number of elements in the array.
Average number of element swaps: n/6 - 1/3 (see
link)
Panics if pivot_index is greater than or equal to n.
Example
use ndarray::array;
use ndarray_stats::Sort1dExt;
let mut data = array![3, 1, 4, 5, 2];
let pivot_index = 2;
let pivot_value = data[pivot_index];
// Partition by the value located at `pivot_index`.
let new_index = data.partition_mut(pivot_index);
// The pivot value is now located at `new_index`.
assert_eq!(data[new_index], pivot_value);
// Elements less than that value are moved to the left.
for i in 0..new_index {
assert!(data[i] < pivot_value);
}
// Elements greater than or equal to that value are moved to the right.
for i in (new_index + 1)..data.len() {
assert!(data[i] >= pivot_value);
}fn __private__(&self, _: PrivateMarker)
fn __private__(&self, _: PrivateMarker)
This method makes this trait impossible to implement outside of
ndarray-stats so that we can freely add new methods, etc., to
this trait without breaking changes.
We don’t anticipate any other crates needing to implement this trait, but if you do have such a use-case, please let us know.
Warning This method is not considered part of the public API, and client code should not rely on it being present. It may be removed in a non-breaking release.