devela::all

Struct Sort

Source 
#[repr(transparent)]
pub struct Sort<T>(pub T);
Expand description

Provides sorting methods for arrays and slices of T, some of them const.

It implements the following methods for sorting exclusive slices: bubble, counting, counting_buf, insertion, merge, quick_lomuto, quick_hoare, quick_3way, quick_selection, quick_shaker.

§Features

When the corresponding feature _sort_f[32|64] or _sort_[iu][8|16|32|64|128] is enabled, It implements the following const methods for sorting copied arrays of primitives: bubble_array, insertion_array, selection_array. In the case of floating-point primitives it uses total ordering.

§Examples

Sort copied arrays of primitives:

let mut arr = [4i32, 7, -5, 1, -13, 0]; // signed primitives
assert_eq![Sort(arr).bubble_array(),    [-13, -5, 0, 1, 4, 7]];
assert_eq![Sort(arr).insertion_array(), [-13, -5, 0, 1, 4, 7]];
assert_eq![Sort(arr).selection_array(), [-13, -5, 0, 1, 4, 7]];

let mut arr = [4u32, 7, 5, 1, 13, 0]; // unsigned primitives
assert_eq![Sort(arr).bubble_array(),    [0, 1, 4, 5, 7, 13]];
assert_eq![Sort(arr).insertion_array(), [0, 1, 4, 5, 7, 13]];
assert_eq![Sort(arr).selection_array(), [0, 1, 4, 5, 7, 13]];

let mut arr = [4.01f32, 7.9, -5.4, 1.0, 0.0, -0.0]; // floating-point primitives
assert_eq![Sort(arr).bubble_array(),    [-5.4, -0.0, 0.0, 1.0, 4.01, 7.9]];
assert_eq![Sort(arr).insertion_array(), [-5.4, -0.0, 0.0, 1.0, 4.01, 7.9]];
assert_eq![Sort(arr).selection_array(), [-5.4, -0.0, 0.0, 1.0, 4.01, 7.9]];

§Performance

The _array suffixed methods calls the cswap macro using the xor swap algorithm, except for the floting-point version which uses a temporary variable.

Tuple Fields§

§0: T

Implementations§

Source§

impl<T: Ord> Sort<&mut [T]>

Source

pub fn bubble(self)

Sorts a slice using bubble sort.

§Examples
let mut data = [4, 7, -5, 1, -13, 0];
Sort(&mut data[..]).bubble();
assert_eq![data, [-13, -5, 0, 1, 4, 7]];
Source

pub fn counting(self) -> Vec<usize> ⓘ
where T: Clone,

Available on crate feature alloc only.

Sorts a slice using counting sort, and returns the ordered frequencies.

Counting sort is particularly efficient when the range of input values is small compared to the number of elements to be sorted.

§Examples
let mut data = [4, 64, 4, 2, 4, 8, 8, 4, 8, 4, 2, 8, 64, 4, 8, 4, 2];
let freq = Sort(&mut data[..]).counting();
assert_eq![data, [2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8, 64, 64]];
assert_eq![freq, [3, 7, 5, 2]];
Source

pub fn counting_buf(self, freq: &mut [T], values: &[T]) -> Option<()> ⓘ
where T: Clone + TryInto<usize> + TryFrom<usize>,

Sorts a slice using counting sort, and writes the frequencies, without allocating.

Counting sort is particularly efficient when the range of input values is small compared to the number of elements to be sorted.

This implementation makes the following assumptions:

  • values contains all distinct values present in self.
  • freq and values are of the same length.
  • freq only contains zeros.

Returns None if values does not contain a value present in self, or if self has more elements than freq can accommodate.

Note that the frequencies in freq will be in the order of the sorted distinct elements in values.

§Examples
let mut data = [4, 64, 4, 2, 4, 8, 8, 4, 8, 4, 2, 8, 64, 4, 8, 4, 2];
let values = [64, 4, 2, 8];
let mut freq = [0; 4];
Sort(&mut data[..]).counting_buf(&mut freq, &values);
assert_eq![data, [64, 64, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 8, 8, 8, 8, 8]];
assert_eq![freq, [2, 7, 3, 5]];
§Panics

Panics in debug if the length of freq and values is not the same.

Source

pub fn insertion(self)

Sorts a slice using insertion sort.

§Examples
let mut arr = [4, 7, -5, 1, -13, 0];
Sort(&mut arr[..]).insertion();
assert_eq![arr, [-13, -5, 0, 1, 4, 7]];
Source

pub fn merge(self)
where T: Copy,

Available on crate feature alloc only.

Sorts a slice using merge sort.

It allocates one vector for the entire sort operation.

§Examples
let mut arr = [4, 7, -5, 1, -13, 0];
Sort(&mut arr[..]).merge();
assert_eq![arr, [-13, -5, 0, 1, 4, 7]];
Source

pub fn selection(self)

Sorts a slice using selection sort.

§Examples
let mut arr = [4, 7, -5, 1, -13, 0];
Sort(&mut arr[..]).selection();
assert_eq![arr, [-13, -5, 0, 1, 4, 7]];
Source

pub fn shaker(self)
where T: Clone,

Sorts a slice using shaker sort.

Also known as cocktail sort and double quicksort.

§Examples
let mut arr = [4, 7, -5, 1, -13, 0];
Sort(&mut arr[..]).shaker();
assert_eq![arr, [-13, -5, 0, 1, 4, 7]];
Source§

impl<'a, T: Ord + 'a> Sort<&'a mut [T]>

Source

pub fn quick_lomuto(slice: &mut [T])

Sorts a slice using quick sort with the Lomuto partition scheme.

It performs more swaps compared to the Hoare partition scheme.

§Examples
let mut arr = [4, 7, -5, 1, -13, 0];
// Sort(&mut arr[..]).quick_lomuto();
Sort::quick_lomuto(&mut arr[..]);
assert_eq![arr, [-13, -5, 0, 1, 4, 7]];
Source

pub fn quick_3way(slice: &mut [T])
where T: Clone,

Sorts a slice using quick sort with the Three way partition scheme.

It is more efficient when dealing with duplicate elements.

§Examples
let mut arr = [4, 7, -5, 1, -13, 0];
Sort::quick_3way(&mut arr);
assert_eq![arr, [-13, -5, 0, 1, 4, 7]];
Source

pub fn quick_hoare(slice: &mut [T])
where T: Clone,

Sorts a slice using quick sort with the Hoare partition scheme.

It performs fewer swaps compared to the Lomuto partition scheme.

§Examples
let mut arr = [4, 7, -5, 1, -13, 0];
Sort::quick_hoare(&mut arr);
assert_eq![arr, [-13, -5, 0, 1, 4, 7]];
Source§

impl<const N: usize> Sort<[i8; N]>

Implement const sorting methods for arrays of primitives.

Source

pub const fn bubble_array(self) -> [i8; N]

Available on crate feature _sort_i8 only.

Returns a copied sorted array using bubble sort.

Source

pub const fn insertion_array(self) -> [i8; N]

Available on crate feature _sort_i8 only.

Returns a copied sorted array using insertion sort.

Source

pub const fn selection_array(self) -> [i8; N]

Available on crate feature _sort_i8 only.

Returns a copied sorted array using insertion sort.

Source§

impl<const N: usize> Sort<[i16; N]>

Implement const sorting methods for arrays of primitives.

Source

pub const fn bubble_array(self) -> [i16; N]

Available on crate feature _sort_i16 only.

Returns a copied sorted array using bubble sort.

Source

pub const fn insertion_array(self) -> [i16; N]

Available on crate feature _sort_i16 only.

Returns a copied sorted array using insertion sort.

Source

pub const fn selection_array(self) -> [i16; N]

Available on crate feature _sort_i16 only.

Returns a copied sorted array using insertion sort.

Source§

impl<const N: usize> Sort<[i32; N]>

Implement const sorting methods for arrays of primitives.

Source

pub const fn bubble_array(self) -> [i32; N]

Available on crate feature _sort_i32 only.

Returns a copied sorted array using bubble sort.

Source

pub const fn insertion_array(self) -> [i32; N]

Available on crate feature _sort_i32 only.

Returns a copied sorted array using insertion sort.

Source

pub const fn selection_array(self) -> [i32; N]

Available on crate feature _sort_i32 only.

Returns a copied sorted array using insertion sort.

Source§

impl<const N: usize> Sort<[i64; N]>

Implement const sorting methods for arrays of primitives.

Source

pub const fn bubble_array(self) -> [i64; N]

Available on crate feature _sort_i64 only.

Returns a copied sorted array using bubble sort.

Source

pub const fn insertion_array(self) -> [i64; N]

Available on crate feature _sort_i64 only.

Returns a copied sorted array using insertion sort.

Source

pub const fn selection_array(self) -> [i64; N]

Available on crate feature _sort_i64 only.

Returns a copied sorted array using insertion sort.

Source§

impl<const N: usize> Sort<[i128; N]>

Implement const sorting methods for arrays of primitives.

Source

pub const fn bubble_array(self) -> [i128; N]

Available on crate feature _sort_i128 only.

Returns a copied sorted array using bubble sort.

Source

pub const fn insertion_array(self) -> [i128; N]

Available on crate feature _sort_i128 only.

Returns a copied sorted array using insertion sort.

Source

pub const fn selection_array(self) -> [i128; N]

Available on crate feature _sort_i128 only.

Returns a copied sorted array using insertion sort.

Source§

impl<const N: usize> Sort<[isize; N]>

Implement const sorting methods for arrays of primitives.

Source

pub const fn bubble_array(self) -> [isize; N]

Available on crate feature _sort_isize only.

Returns a copied sorted array using bubble sort.

Source

pub const fn insertion_array(self) -> [isize; N]

Available on crate feature _sort_isize only.

Returns a copied sorted array using insertion sort.

Source

pub const fn selection_array(self) -> [isize; N]

Available on crate feature _sort_isize only.

Returns a copied sorted array using insertion sort.

Source§

impl<const N: usize> Sort<[u8; N]>

Source

pub const fn bubble_array(self) -> [u8; N]

Available on crate feature _sort_u8 only.

Returns a copied sorted array using bubble sort.

Source

pub const fn insertion_array(self) -> [u8; N]

Available on crate feature _sort_u8 only.

Returns a copied sorted array using insertion sort.

Source

pub const fn selection_array(self) -> [u8; N]

Available on crate feature _sort_u8 only.

Returns a copied sorted array using selection sort.

Source§

impl<const N: usize> Sort<[u16; N]>

Source

pub const fn bubble_array(self) -> [u16; N]

Available on crate feature _sort_u16 only.

Returns a copied sorted array using bubble sort.

Source

pub const fn insertion_array(self) -> [u16; N]

Available on crate feature _sort_u16 only.

Returns a copied sorted array using insertion sort.

Source

pub const fn selection_array(self) -> [u16; N]

Available on crate feature _sort_u16 only.

Returns a copied sorted array using selection sort.

Source§

impl<const N: usize> Sort<[u32; N]>

Source

pub const fn bubble_array(self) -> [u32; N]

Available on crate feature _sort_u32 only.

Returns a copied sorted array using bubble sort.

Source

pub const fn insertion_array(self) -> [u32; N]

Available on crate feature _sort_u32 only.

Returns a copied sorted array using insertion sort.

Source

pub const fn selection_array(self) -> [u32; N]

Available on crate feature _sort_u32 only.

Returns a copied sorted array using selection sort.

Source§

impl<const N: usize> Sort<[u64; N]>

Source

pub const fn bubble_array(self) -> [u64; N]

Available on crate feature _sort_u64 only.

Returns a copied sorted array using bubble sort.

Source

pub const fn insertion_array(self) -> [u64; N]

Available on crate feature _sort_u64 only.

Returns a copied sorted array using insertion sort.

Source

pub const fn selection_array(self) -> [u64; N]

Available on crate feature _sort_u64 only.

Returns a copied sorted array using selection sort.

Source§

impl<const N: usize> Sort<[u128; N]>

Source

pub const fn bubble_array(self) -> [u128; N]

Available on crate feature _sort_u128 only.

Returns a copied sorted array using bubble sort.

Source

pub const fn insertion_array(self) -> [u128; N]

Available on crate feature _sort_u128 only.

Returns a copied sorted array using insertion sort.

Source

pub const fn selection_array(self) -> [u128; N]

Available on crate feature _sort_u128 only.

Returns a copied sorted array using selection sort.

Source§

impl<const N: usize> Sort<[usize; N]>

Source

pub const fn bubble_array(self) -> [usize; N]

Available on crate feature _sort_usize only.

Returns a copied sorted array using bubble sort.

Source

pub const fn insertion_array(self) -> [usize; N]

Available on crate feature _sort_usize only.

Returns a copied sorted array using insertion sort.

Source

pub const fn selection_array(self) -> [usize; N]

Available on crate feature _sort_usize only.

Returns a copied sorted array using selection sort.

Source§

impl<const N: usize> Sort<[f32; N]>

Source

pub const fn bubble_array(self) -> [f32; N]

Available on crate feature _sort_f32 only.

Returns a copied sorted array using bubble sort.

Source

pub const fn insertion_array(self) -> [f32; N]

Available on crate feature _sort_f32 only.

Returns a copied sorted array using insertion sort.

Source

pub const fn selection_array(self) -> [f32; N]

Available on crate feature _sort_f32 only.

Returns a copied sorted array using selection sort.

Source§

impl<const N: usize> Sort<[f64; N]>

Source

pub const fn bubble_array(self) -> [f64; N]

Available on crate feature _sort_f64 only.

Returns a copied sorted array using bubble sort.

Source

pub const fn insertion_array(self) -> [f64; N]

Available on crate feature _sort_f64 only.

Returns a copied sorted array using insertion sort.

Source

pub const fn selection_array(self) -> [f64; N]

Available on crate feature _sort_f64 only.

Returns a copied sorted array using selection sort.

Auto Trait Implementations§

§

impl<T> Freeze for Sort<T>
where T: Freeze,

§

impl<T> RefUnwindSafe for Sort<T>
where T: RefUnwindSafe,

§

impl<T> Send for Sort<T>
where T: Send,

§

impl<T> Sync for Sort<T>
where T: Sync,

§

impl<T> Unpin for Sort<T>
where T: Unpin,

§

impl<T> UnwindSafe for Sort<T>
where T: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
§

impl<T> ArchivePointee for T

§

type ArchivedMetadata = ()

The archived version of the pointer metadata for this type.
§

fn pointer_metadata( _: &<T as ArchivePointee>::ArchivedMetadata, ) -> <T as Pointee>::Metadata

Converts some archived metadata to the pointer metadata for itself.
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> ByteSized for T

Source§

const BYTE_ALIGN: usize = _

The alignment of this type in bytes.
Source§

const BYTE_SIZE: usize = _

The size of this type in bytes.
Source§

fn byte_align(&self) -> usize ⓘ

Returns the alignment of this type in bytes.
Source§

fn byte_size(&self) -> usize ⓘ

Returns the size of this type in bytes. Read more
Source§

fn ptr_size_ratio(&self) -> [usize; 2]

Returns the size ratio between Ptr::BYTES and BYTE_SIZE. Read more
Source§

impl<T, R> Chain<R> for T
where T: ?Sized,

Source§

fn chain<F>(self, f: F) -> R
where F: FnOnce(Self) -> R, Self: Sized,

Chain a function which takes the parameter by value.
Source§

fn chain_ref<F>(&self, f: F) -> R
where F: FnOnce(&Self) -> R,

Chain a function which takes the parameter by shared reference.
Source§

fn chain_mut<F>(&mut self, f: F) -> R
where F: FnOnce(&mut Self) -> R,

Chain a function which takes the parameter by exclusive reference.
Source§

impl<T> ExtAny for T
where T: Any + ?Sized,

Source§

fn type_id() -> TypeId

Returns the TypeId of Self. Read more
Source§

fn type_of(&self) -> TypeId

Returns the TypeId of self. Read more
Source§

fn type_name(&self) -> &'static str ⓘ

Returns the type name of self. Read more
Source§

fn type_is<T: 'static>(&self) -> bool

Returns true if Self is of type T. Read more
Source§

fn as_any_ref(&self) -> &dyn Any
where Self: Sized,

Upcasts &self as &dyn Any. Read more
Source§

fn as_any_mut(&mut self) -> &mut dyn Any
where Self: Sized,

Upcasts &mut self as &mut dyn Any. Read more
Source§

fn as_any_box(self: Box<Self>) -> Box<dyn Any>
where Self: Sized,

Upcasts Box<self> as Box<dyn Any>. Read more
Source§

fn downcast_ref<T: 'static>(&self) -> Option<&T> ⓘ

Available on crate feature unsafe_layout only.
Returns some shared reference to the inner value if it is of type T. Read more
Source§

fn downcast_mut<T: 'static>(&mut self) -> Option<&mut T> ⓘ

Available on crate feature unsafe_layout only.
Returns some exclusive reference to the inner value if it is of type T. Read more
Source§

impl<T> ExtMem for T
where T: ?Sized,

Source§

const NEEDS_DROP: bool = _

Know whether dropping values of this type matters, in compile-time.
Source§

fn mem_align_of<T>() -> usize ⓘ

Returns the minimum alignment of the type in bytes. Read more
Source§

fn mem_align_of_val(&self) -> usize ⓘ

Returns the alignment of the pointed-to value in bytes. Read more
Source§

fn mem_size_of<T>() -> usize ⓘ

Returns the size of a type in bytes. Read more
Source§

fn mem_size_of_val(&self) -> usize ⓘ

Returns the size of the pointed-to value in bytes. Read more
Source§

fn mem_copy(&self) -> Self
where Self: Copy,

Bitwise-copies a value. Read more
Source§

fn mem_needs_drop(&self) -> bool

Returns true if dropping values of this type matters. Read more
Source§

fn mem_drop(self)
where Self: Sized,

Drops self by running its destructor. Read more
Source§

fn mem_forget(self)
where Self: Sized,

Forgets about self without running its destructor. Read more
Source§

fn mem_replace(&mut self, other: Self) -> Self
where Self: Sized,

Replaces self with other, returning the previous value of self. Read more
Source§

fn mem_take(&mut self) -> Self
where Self: Default,

Replaces self with its default value, returning the previous value of self. Read more
Source§

fn mem_swap(&mut self, other: &mut Self)
where Self: Sized,

Swaps the value of self and other without deinitializing either one. Read more
Source§

unsafe fn mem_zeroed<T>() -> T

Available on crate feature unsafe_layout only.
Returns the value of type T represented by the all-zero byte-pattern. Read more
Source§

unsafe fn mem_transmute_copy<Src, Dst>(src: &Src) -> Dst

Available on crate feature unsafe_layout only.
Returns the value of type T represented by the all-zero byte-pattern. Read more
Source§

fn mem_as_bytes(&self) -> &[u8] ⓘ
where Self: Sync + Unpin,

Available on crate feature unsafe_slice only.
View a Sync + Unpin self as &[u8]. Read more
Source§

fn mem_as_bytes_mut(&mut self) -> &mut [u8] ⓘ
where Self: Sync + Unpin,

Available on crate feature unsafe_slice only.
View a Sync + Unpin self as &mut [u8]. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

§

impl<S> FromSample<S> for S

§

fn from_sample_(s: S) -> S

Source§

impl<T> Hook for T

Source§

fn hook_ref<F>(self, f: F) -> Self
where F: FnOnce(&Self),

Applies a function which takes the parameter by shared reference, and then returns the (possibly) modified owned value. Read more
Source§

fn hook_mut<F>(self, f: F) -> Self
where F: FnOnce(&mut Self),

Applies a function which takes the parameter by exclusive reference, and then returns the (possibly) modified owned value. Read more
§

impl<T> Instrument for T

§

fn instrument(self, span: Span) -> Instrumented<Self> ⓘ

Instruments this type with the provided Span, returning an Instrumented wrapper. Read more
§

fn in_current_span(self) -> Instrumented<Self> ⓘ

Instruments this type with the current Span, returning an Instrumented wrapper. Read more
Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> IntoEither for T

Source§

fn into_either(self, into_left: bool) -> Either<Self, Self> ⓘ

Converts self into a Left variant of Either<Self, Self> if into_left is true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
Source§

fn into_either_with<F>(self, into_left: F) -> Either<Self, Self> ⓘ
where F: FnOnce(&Self) -> bool,

Converts self into a Left variant of Either<Self, Self> if into_left(&self) returns true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
§

impl<F, T> IntoSample<T> for F
where T: FromSample<F>,

§

fn into_sample(self) -> T

§

impl<T> LayoutRaw for T

§

fn layout_raw(_: <T as Pointee>::Metadata) -> Result<Layout, LayoutError> ⓘ

Returns the layout of the type.
§

impl<T, N1, N2> Niching<NichedOption<T, N1>> for N2
where T: SharedNiching<N1, N2>, N1: Niching<T>, N2: Niching<T>,

§

unsafe fn is_niched(niched: *const NichedOption<T, N1>) -> bool

Returns whether the given value has been niched. Read more
§

fn resolve_niched(out: Place<NichedOption<T, N1>>)

Writes data to out indicating that a T is niched.
§

impl<T> Pointable for T

§

const ALIGN: usize

The alignment of pointer.
§

type Init = T

The type for initializers.
§

unsafe fn init(init: <T as Pointable>::Init) -> usize ⓘ

Initializes a with the given initializer. Read more
§

unsafe fn deref<'a>(ptr: usize) -> &'a T

Dereferences the given pointer. Read more
§

unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

Mutably dereferences the given pointer. Read more
§

unsafe fn drop(ptr: usize)

Drops the object pointed to by the given pointer. Read more
§

impl<T> Pointee for T

§

type Metadata = ()

The metadata type for pointers and references to this type.
§

impl<T, U> ToSample<U> for T
where U: FromSample<T>,

§

fn to_sample_(self) -> U

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error> ⓘ

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error> ⓘ

Performs the conversion.
§

impl<T> WithSubscriber for T

§

fn with_subscriber<S>(self, subscriber: S) -> WithDispatch<Self> ⓘ
where S: Into<Dispatch>,

Attaches the provided Subscriber to this type, returning a WithDispatch wrapper. Read more
§

fn with_current_subscriber(self) -> WithDispatch<Self> ⓘ

Attaches the current default Subscriber to this type, returning a WithDispatch wrapper. Read more
§

impl<S, T> Duplex<S> for T
where T: FromSample<S> + ToSample<S>,

§

impl<T> Ungil for T
where T: Send,