[−][src]Function sorting_rs::smooth_sort::smooth_sort
pub fn smooth_sort<T: PartialOrd>(input: &mut [T])
Sorts a slice in-place using Smooth sort
All kinds of slices can be sorted as long as they implement
PartialOrd
.
This sorting algorithm transforms the input array into implicit heap data structure and then produces the sorted array by repeatedly extracting the largest remaining element This algorithm makes use of Leonardo numbers. It's a sequence of numbers defined by:
L(0) = 1
L(1) = 1
L(n) = L(n - 1) + L(n - 2) + 1
*OR*
L(n) = 2 * Fib(n + 1) - 1
Where + 1 is "add" number and "Fib" are Fibonacci numbers
For 64-bit systems it's possible to use 90 Leonardo numbers placed as a constant array [usize; 90]
Examples
let mut vec = vec![5,3,2,4]; sorting_rs::smooth_sort(&mut vec); assert_eq!(vec, &[2,3,4,5]);
let mut strings = vec!["rustc", "cargo", "rustup"]; sorting_rs::smooth_sort(&mut strings); assert_eq!(strings, &["cargo", "rustc", "rustup"]);