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].
(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()
.
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
Thanks. I am a new user of rust. I will learn more.
Thanks a lot. I should read more API reference.
Thanks. I try and it works.