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

#1

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?

#2

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.

#3

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.

#4

If it helps, you can check out a working insertion sort at https://github.com/BurntSushi/rust-sorts/blob/master/src/lib.rs#L44-L55. 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.

#5

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