This post is about the sorting algorithm called Insertion Sort using recursion and iteration in Rust. It is simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
Sort Using Recursion
Our codes have 2 functions. The first function only runs a recursive function.
1 2 3 4 5 | // Call this from some main function fn insertion_sort_recursive(param_int_array:&mut [i32]) { // We need to specify the first index insertion_sort_recursive_process(param_int_array, 1); } |
The second function is the actual Insertion Sort function that uses recursion. It will call itself a number of times until the index + 1 is equals to or grater than the array length.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | fn insertion_sort_recursive_process(param_int_array:&mut [i32], index: usize) { let value = param_int_array[index]; let mut j = index; while j > 0 && param_int_array[j - 1] > value { param_int_array[j] = param_int_array[j - 1]; j-=1; } param_int_array[j] = value; if index + 1 < param_int_array.len() { insertion_sort_recursive_process(param_int_array, index + 1) } } |
Below is an example of codes that use our bootstrap function.
1 2 3 4 5 | fn main() { let mut int_values_array = [1, 0, 9, 4, 8, 177, 8, 5, 6,7 , 4, 3, 2, 1]; insertion_sort_recursive(&mut int_values_array); println!("{:?}", int_values_array); } |
The codes output the following.
1 | [0, 1, 1, 2, 3, 4, 4, 5, 6, 7, 8, 8, 9, 177] |
Sort Using Iteration
For this example, we have a function that accepts a mutable reference to an array of i32’s with any length and returns nothing. This is the only function of the Insertion Sort using iteration. Notice that it only relies on a loop and does not call itself a number of times until an condition is met.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | fn insertion_sort_iterative(param_int_array:&mut [i32]) { // We start off at the second index let mut i = 1; // Get the length to the array let array_len = param_int_array.len(); // Loop until we reach the length value of the array while i < array_len { let value = param_int_array[i]; let mut j = i; // Compare the two values and perform swap if needed while j > 0 && param_int_array[j - 1] > value { param_int_array[j] = param_int_array[j - 1]; j-=1; } param_int_array[j] = value; i+=1; } } |
A sample usage would be:
1 2 3 4 5 | fn main() { let mut int_values_array:[i32; 11] = [1, 0, 9, 8, 5, 6,7 , 4, 3, 2, 1]; insertion_sort_iterative(&mut int_values_array); println!("{:?}", int_values_array); } |
This is the output of the Insertion Sort using iteration. Obviously, the output is the same using recursion.
1 | [0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9] |
Other Algorithms in Rust
For more algorithms in Rust, please go to Algorithms In Codes page.
