insertion Algorithm
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.
However, insertion sort provides several advantages:
Simple implementation: Jon Bentley shows a three-line c version, and a five-line optimized version
Efficient for (quite) small data sets, much like other quadratic sorting algorithmsAdaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each component in the input is no more than K places away from its sorted position
Stable; i.e., makes not change the relative order of components with equal keys
use std::cmp;
#[allow(dead_code)]
pub fn insertion_sort<T>(arr: &[T]) -> Vec<T>
where
T: cmp::PartialEq + cmp::PartialOrd + Clone,
{
// The resulting vector should contain the same amount of elements as
// the slice that is being sorted, so enough room is preallocated
let mut result: Vec<T> = Vec::with_capacity(arr.len());
// Iterate over the elements to sort and
// put a clone of the element to insert in elem.
for elem in arr.iter().cloned() {
// How many elements have already been inserted?
let n_inserted = result.len();
// Loop over the inserted elements and one more index.
for i in 0..=n_inserted {
// If at the end or result[i] is larger than the current element,
// we have found the right spot:
if i == n_inserted || result[i] > elem {
// Insert the element at i,
// move the rest to higher indexes:
result.insert(i, elem);
break;
}
}
}
result
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn empty() {
let res = insertion_sort(&Vec::<u8>::new());
assert_eq!(res, vec![]);
}
#[test]
fn one_element() {
let res = insertion_sort(&vec!["a"]);
assert_eq!(res, vec!["a"]);
}
#[test]
fn already_sorted() {
let res = insertion_sort(&vec!["a", "b", "c"]);
assert_eq!(res, vec!["a", "b", "c"]);
}
#[test]
fn basic() {
let res = insertion_sort(&vec!["d", "a", "c", "b"]);
assert_eq!(res, vec!["a", "b", "c", "d"]);
}
#[test]
fn odd_number_of_elements() {
let res = insertion_sort(&vec!["d", "a", "c", "e", "b"]);
assert_eq!(res, vec!["a", "b", "c", "d", "e"]);
}
#[test]
fn repeated_elements() {
let res = insertion_sort(&vec![542, 542, 542, 542]);
assert_eq!(res, vec![542, 542, 542, 542]);
}
}
