Skip to content

Instantly share code, notes, and snippets.

@endenis
Forked from mgadzhi/insertion_sort.rs
Last active August 29, 2015 14:13
Show Gist options
  • Save endenis/25b3b9e5cd3b3f002178 to your computer and use it in GitHub Desktop.
Save endenis/25b3b9e5cd3b3f002178 to your computer and use it in GitHub Desktop.
fn swap(arr: &mut Vec<int>, i: uint, j: uint) -> &Vec<int> {
let buf = arr[i];
arr[i] = arr[j];
arr[j] = buf;
arr
}
fn insertion_sort1(arr: &mut Vec<int>) -> &Vec<int> {
for i in range(1, arr.len()) {
let key = arr[i];
let mut j = (i - 1) as int;
let mut j_u = j as uint;
while j >= 0 && arr[j_u] > key {
arr[j_u + 1] = arr[j_u];
j = j - 1;
j_u = j as uint;
}
arr[j_u + 1] = key;
}
arr
}
fn insertion_sort2(arr: &mut Vec<int>) -> &Vec<int> {
for i in range(1, arr.len()) {
let mut j = i;
while j > 0 && arr[j] < arr[j - 1] {
swap(arr, j, j - 1);
j = j - 1;
}
}
arr
}
fn main() {
let mut original1 = vec![5, 8, 6, 3, 7, 0, 4, 1];
let mut original2 = original1.clone();
println!("Original array: {}", original1);
insertion_sort1(&mut original1);
println!("Insertionsort1: {}", original1);
insertion_sort2(&mut original2);
println!("Insertionsort2: {}", original2);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment