Struct Sort

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

🌐 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

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

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]];

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]];

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.

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]];

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]];

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]];

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]];

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

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]];

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]];

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]];