Trait ndarray_stats::Sort1dExt[−][src]

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);
}

Methods for sorting and partitioning 1-D arrays.

Required methods

fn get_from_sorted_mut(&mut self, i: usize) -> A where
    A: Ord + Clone,
    S: DataMut, [src]

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.

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>, [src]

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..

fn partition_mut(&mut self, pivot_index: usize) -> usize where
    A: Ord + Clone,
    S: DataMut, [src]

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)[src]

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.

Loading content...

Implementations on Foreign Types

impl<A, S> Sort1dExt<A, S> for ArrayBase<S, Ix1> where
    S: Data<Elem = A>, [src]

Loading content...

Implementors

Loading content...