Thread '<main>' panics when I try to access first element of slice

Hi all! I'm trying to implement a few algorithms from CLRS to learn rust, and as a refresher on Algorithms. On trying to make a naive implementation of Insertion Sort, as shown below:

// will sort on key.
struct Record {
  key: i64
}

fn insertion_sort(records: &mut [&Record]) {
  for i in 1..records.len() {
    let r :&Record = records[i].clone();
    let mut j = i - 1;
    while j >= 0 && records[j].key > r.key {
      records[j+1] = records[j];
      j = j - 1;
    }
    records[j+1] = r;
  }
}

fn main() {
  // let records: &mut[&Record] = &mut[];
  // let records : &mut[&Record] = &mut[ &Record{key:10}];
  let records : &mut[&Record] = &mut[ &Record{key:1200}, &Record{key:99999},
                                      &Record{key:1200}, &Record{key:451},
                                      &Record{key:90240}, &Record{key:4},
                                      &Record{key:20}, &Record{key:78}, ];

  insertion_sort(records);
  for r in records {
    println!("{}", r.key);
  }
}

This code compiles, but with the warning

warning: comparison is useless due to type limits, #[warn(unused_comparisons)] on by default
src/main.rs:10     while j >= 0 && records[j].key > r.key {

and when run gets the error

thread '<main>' panicked at 'arithmetic operation overflowed', src/main.rs:12
Process didn't exit successfully: `target/debug/001-insertion-sort` (exit code: 101)

I've been smashing my head on the keyboard all weekend, but I can't for the life of me see what's wrong. A statement-for-statement translation in C runs without a problem.

Is there something I'm missing?

The expression records.len() is a usize, therefore the type of i is automatically inferred as usize. Same for j.

When i is equal to 1 and you do j = j - 1, the value of j would need to become -1. Rust detects this and panicks.
That's also why you have a warning for if j >= 0. This condition can only be true.

To fix this problem, you can just add if j == 0 { break; } inside your loop.

2 Likes

Thanks! If I insert the break, the panic goes away, but the first element always remains in its original position, regardless of whether it's greater than the other elements. I'll try to find out what could be the problem and update the thread.

If it helps, you can check out a working insertion sort at rust-sorts/lib.rs at master · BurntSushi/rust-sorts · GitHub. I think it is not exactly idiomatic (probably want a for i in 1..xs.len() and TotalOrd is now just Ord), but it should get you far enough along.

Thanks, I will definitely take a look. It will feel like cheating, though. :smile:

I realize that my reply is woefully out of date, however I found this thread because I believe I'm trying to solve the same problem that the OP was. I thought I would try and kill 2 birds with one stone, I thought I would learn about algorithms in the "Introduction to Algorithms" book, third edition while at the same time learn more about Rust. I think this may have been a bad idea. I thought I was not understanding something fundamental in the book's explanation of insertion sort. It turns out that I have been fighting Rust's type system. I'm a JavaScript developer by day and when I finally tried the solution there, everything just worked. With that knowledge in hand and a bit more googling, I was able to come up with the following Rust solution to this problem:

fn insertion_sort(unsorted: &mut [i32]) {
    println!("{:?}", unsorted);

    for j in 1..unsorted.len() {
        let key = unsorted[j];
        let mut i = j - 1;

        while i as i32 > -1 && unsorted[i] > key {
            unsorted[i + 1] = unsorted[i];
            unsorted[i] = key;

            if i == 0 {
                break;
            }

            i = i - 1;
        }
    }

    println!("{:?}", unsorted);
}

fn main() {
    let mut unsorted = vec![5, 2, 4, 6, 1, 3]; // mutable

    insertion_sort(&mut unsorted);
}

This solution doesn't follow the pseudo code exactly, but it's the closest I've seen.
I do hope this helps the next poor soul that has the same crazy idea :slight_smile: