rust_sort/
insertion_sort.rs

1use super::Sortable;
2
3/// Insertion sorts in-place, stable, in ascending order, a mutable ref slice of type T: Sortable
4///
5/// Insertion sort loops over an unsorted collection one element at a time to build
6/// a sorted collection starting as a single element at the beginning. At each loop iteration,
7/// the current element is put in its right order within the beginning of the collection,
8/// by pushing elements greater than itself to the right. The sorted portion of the collection grows until
9/// there are no unsorted items left.
10///
11/// # Examples
12///
13/// ```
14/// use rust_sort::insertion_sort::sort;
15///
16/// let mut arr = [3, 2, 1, 7, 9, 4, 1, 2];
17/// sort(&mut arr);
18/// assert_eq!(arr, [1, 1, 2, 2, 3, 4, 7, 9]);
19///
20/// ```
21pub fn sort<T: Sortable>(list: &mut [T]) {
22    let len = list.len();
23    if len <= 1 {
24        return;
25    }
26
27    for i in 1..len {
28        let mut j = i;
29        while j > 0 && list[j] < list[j-1]{
30            list.swap(j, j-1);
31            j -=1;
32        }
33    }
34}
rust_sort/insertion_sort.rs

rust_sort/
insertion_sort.rs
