Table of content

Insertion Sort in Rust

Insertion sort is one of the simplest sorting methods. Compared to efficient sorting methods such as quicksort, the processing of large data is less than ideal. The algorithm is to insert the elements to be sorted directly into the correct position, hence the name.

The basic characteristics of the Insertion sort are as follows:

The implementation is simple and easy to understand.

  • It is more efficient when the amount of data is small and is more efficient than other $O(n^2) $ sorting sorts (bubble sort).
  • Adaptive sorting : Accelerate sorting according to the current data sorting situation. The closer the data is to the sorting, the higher the efficiency.
  • Stable sorting : Elements of the same key value, the relative position does not change after sorting.
    In-place sorting: no additional storage space to sort.
  • Real-time algorithm : It can process data input step by step without waiting for the data to be completely prepared.
/// Insertion sort.

pub fn insertion_sort(arr: &mut [i32]) { for i in 1..arr.len() { let mut j = i; while j > 0 && arr[j - 1] > arr[j] { arr.swap(j - 1, j); j -= 1; } } }

/// Binary insertion sort.

/// Binary insertion sort is a insertion sort variant that utilizes binary

/// search to reduce comparisons in a normal insertion sort.

pub fn binary_insertion_sort(arr: &mut [i32]) { for i in 1..arr.len() { let val = arr[i]; let mut j = i; let pos = arr[..i].binary_search(&val).unwrap_or_else(|pos| pos); // Swap all elements until specific position. while j > pos { arr.swap(j - 1, j); j -= 1; } } }

#[cfg(test)]

mod base { use super::*; base_cases!(insertion_sort); }

#[cfg(test)]

mod binary_insertion { use super::*; base_cases!(binary_insertion_sort); }

Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions