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

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.

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.

Implementations on Foreign Types

Implementors