insertion_sort.rs

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);
}