Algorithms Insert-Sort [Rust]

For educational purposes I started a new training program for myself. I want to solve / program at least 1 algorithm a day. Not just copy paste implementation but iterating through different languages per algorithm as well.

The reason to switch the languages per algorithm is fairly simple using a different languages seams to be manageable. I do the same on hacker rank because solving something easily is for me not challenging yourself enough.

So I started with Rust and the insert-sort. I wanted to reflect on the algorithm as well. As you may know really understanding something can be challenging and I'm old so I actually use these story as dummy reflections.

Explaining things uses 70% of the brain so you learn the most because you reformulate and visualize a topic over and over again what I do here is commonly known a rubber ducking because I don't expect an answer :)

So what does the insert-sort do in layman terms ? it does compare to values inside of a composite datatype and moves the bigger ones to the beginning or end of the structure.

I picked rust because I read a lot about it's memory model and it's one of my next languages to learn.

Ofc as it is with every new language you spend most of the getting the code to compile/run and not solving the problem

main.rs:15:9: 15:20 error: unable to infer enough type information about _; type annotations or > generic parameter binding required [E0282] main.rs:15 let mut h_value; ^~~ main.rs:15:9: 15:20 help: run rustc --explain E0282 to see a detailed explanation error: aborting due to previous error

Which can be annoying esp the idea of ownership and borrowing will still take a while to sink in.

I'm 100% sure this can be solved a lot more elegant than what I did here. Esp the part where I used a slice to get a mutable array copy to work with.

Edit: About the algorithm, it has an O(n²) average time complexity which is kinda slow and the worst case as well :) with a pre-ordered set it will take O(n) with normal array operations or O(1) if you do address arithmetic "swapping addresses".

a space complexity with O(n) or O(1) with swaps is good to nice :) we want O(1) if possible but not every language allows you to go low level and swap addresses spaces in the heap or stack.

fn main() {
        let set : [i32; 15] = [44, 15, 22, 10, 8, 44, 66, 1000, 878, 9, 3, 12, 84, 15, 33];
        print_int_array(insert_sort(&set));
}

// basic insert sort
fn insert_sort(set : & [i32]) -> [i32; 15]
{
    let mut r_set : [i32; 15] = [0;15];
    r_set.clone_from_slice(&set);
    let mut j;
    let mut i = 0;
    let mut h_value;

    while i < r_set.len()-1 {
        j = i+1;
        while j > 0  && r_set[j-1] > r_set[j]{
            h_value = r_set[j];
            r_set[j] = r_set[j-1];
            r_set[j-1] = h_value;
            j = j-1;
        }

        i = i+1;
    }

    return r_set;
}

fn print_int_array(set : [i32; 15]) {
    for x in set.iter() {
        println!("{}", x);
    }
}

So what's happening ? main() is the common entry point like in many other languages if it's java or C or go :)

let gets you a read only variable which i typed to be integer 32bit and having a length of 15 fields which means at least 60Bytes of memory in the heap are allocated for this array.

let set : [i32; 15] = [44, 15, 22, 10, 8, 44, 66, 1000, 878, 9, 3, 12, 84, 15, 33];

if i don't initialize it's just declared but empty so I cannot access it. I than call insert_sort and pass the set variable as a reference (the allocated memory still remains on the heap and only the access writes are passed into the function.)

inside of the insert_sort i declare an array that's mutable and initialize it from position 0 to 15 with zeros.

 let mut r_set : [i32; 15] = [0;15];

after that I deep copy the set array into my r_set so i have the immutable set value in my mutable array.

r_set.clone_from_slice(&set);

next I need 3 mutable integers 3 helpers, 2 for positioning inside of the nested while loops and 1 as a buffer for the copy operations;

    let mut j;
    let mut i = 0;
    let mut h_value;

what follows next is pretty simple I start the outer loop (check if i is smaller than length-1, because j will get out of boundary otherwise) set the second position j to 1 and start the nested loop that checks if A: j is bigger than zero and B: the value in the set on position j-1 is bigger than the value of the position j (1 -> 44 > 15) which is true so we get into the nested loop.

while i < r_set.len()-1 {
        j = i+1;
        while j > 0  && r_set[j-1] > r_set[j]{

now the helper value gets the higher position value and the position will be overwritten by the lower position value and than copied from the helper to the lower position or simpler put they've been swapped

  while j > 0  && r_set[j-1] > r_set[j]{
            h_value = r_set[j];
            r_set[j] = r_set[j-1];
            r_set[j-1] = h_value;

Now i decrement j by 1 and start the check which is now obviously 0 since this is on part of the termination clause the loop is stopped and I'm in the outer loop again. j = j-1;

I increment the starting position by 1 and the procedure starts again. i = i+1;

That's all pretty basic and straight forward and was fun to implement :) at least most of the time :D

Maybe I forgot something or I did something wrong :) if you got better solutions please let me know :) as I mentioned I just started with rust :). Please mention it in the comments I will correct it asap :)

The next one will be bubble sort and I think I will do it in C.