Reference and Borrowing problem with Generics type Vec<T>: a[i] = a[i+1]


#1

I write insertion-sort code according to book: Introduction to Algorithms.
when type is defined, it can work.
But when I want to use Generics type in code, it can’t work. Code and compile information like this:

use std::cmp::PartialOrd;

pub mod insertion_sort {
pub fn insertion_sort<T: PartialOrd>(a: &mut Vec) {
for j in 1…a.len() {
let key = &a[j];
let mut i = j - 1;
while i > 0 && a[i] > *key {
let mut tmp = &mut a[i];
a[i+1] = *tmp;
i = i - 1;
}

        a[i+1] = *key;
    }
}

}

I know the reason is that complier don’t know generic type is have copy trait or not, but I don’t know how to
make it that moving elements of Vec type with generics like this: a[i+1] = a[i].


#2

(Readability note: put triple-backticks around your code to format it nicely. It also seems that some code got lost, e.g. the generic type after fn insertion_sort.)

In general, if your type is not Copy, you cannot just move a[i+1] = a[i] since that would leave a “hole” in place of a[i]. You should at least require that the generic type is Clone, so that you can do a[i+1] = a[i].clone().


#3

To avoid the Copy or Clone requirement, you can Vec::swap elements in the second loop (kinda like a hybrid of bubble and insertion sort) since in safe rust, it’s difficult to deal with uninitialized array elements since it’s difficult to guarantee safety. This swap is just a bit-swap instead of a deep clone. If you have a vector of very large structs (as reported by std::mem::size_of), then you could sort indices instead and reconstruct an array, but that requires allocating space for the indices up front.

Here’s the while loop variant (with an off-by-1 error in the original code corrected) and a for-loop version that’s using indices similar to yours but without needing to worry about unsigned underflow:

pub fn insertion_sort<T: Ord>(a: &mut Vec<T>) {
    for j in 1..a.len() {
        let mut i = j;
        while i > 0 && a[i] < a[i-1] {
            a.swap(i, i-1);
            i = i - 1;
        }
    }
}

pub fn insertion_sort2<T: Ord>(a: &mut Vec<T>) {
    for j in 1..a.len() {
        for i in (0..j).rev() {
            if a[i+1] >= a[i] { break; }
            a.swap(i+1, i);
        }
    }
}

Playground link with interleaved print statements


#4

Thanks. I am a new user of rust. I will learn more.


#5

Thanks a lot. I should read more API reference.


#6

Thanks. I try and it works.