Trait ndarray_stats::Sort1dExt
source · pub trait Sort1dExt<A, S>where
S: Data<Elem = A>,{
fn sorted_get_mut(&mut self, i: usize) -> A
where
A: Ord + Clone,
S: DataMut;
fn partition_mut(&mut self, pivot_index: usize) -> usize
where
A: Ord + Clone,
S: DataMut;
}
Expand description
Methods for sorting and partitioning 1-D arrays.
Required Methods
sourcefn sorted_get_mut(&mut self, i: usize) -> Awhere
A: Ord + Clone,
S: DataMut,
fn sorted_get_mut(&mut self, i: usize) -> Awhere
A: Ord + Clone,
S: DataMut,
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
.
sourcefn partition_mut(&mut self, pivot_index: usize) -> usizewhere
A: Ord + Clone,
S: DataMut,
fn partition_mut(&mut self, pivot_index: usize) -> usizewhere
A: Ord + Clone,
S: DataMut,
Return the index of self[partition_index]
if self
were to be sorted
in increasing order.
self
elements are rearranged in such a way that self[partition_index]
is in the position it would be in an array sorted in increasing order.
All elements smaller than self[partition_index]
are moved to its
left and all elements equal or greater than self[partition_index]
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 partition_index
is greater than or equal to n
.