I was trying to implement quicksort algorithm in a purely iterable manner:
initial code
fn _partition<T: Ord>(slice: &mut [T], mut i: usize) -> Option<usize> {
loop {
let (left, right) = slice.split_at_mut(i);
i = if let Some((pivot, right)) = right.split_first_mut() {
let mut left_iter = left.iter_mut().enumerate();
let mut right_iter = right.iter_mut().enumerate().rev();
loop {
if let Some((l, lele)) = left_iter.by_ref().find(|(_, ele)| ele > &pivot) {
if let Some((_, rele)) = right_iter.by_ref().find(|(_, ele)| ele < &pivot) {
std::mem::swap(lele, rele);
} else {
std::mem::swap(pivot, lele);
break l
}
} else {
if let Some((r, rele)) = right_iter.by_ref().find(|(_, ele)| ele < &pivot) {
std::mem::swap(pivot, rele);
break i + r
} else {
return Some(i)
}
}
}
} else {
return None
}
}
}
fn partition<T: Ord>(slice: &mut [T]) -> Option<usize> {
let len = slice.len();
let pivot = len / 2;
_partition(slice, pivot)
}
fn quick_sort<T: Ord>(slice: &mut [T]) {
partition(slice).map(|i| {
let (left, right) = slice.split_at_mut(i);
quick_sort(left);
right.split_first_mut().map(|(_, right)| quick_sort(right))
});
}
It works correctly and passes all the tests(here)
However, I modified the code like this:
fn _partition<T: Ord>(slice: &mut [T], mut i: usize) -> Option<(&mut [T], &mut [T])> {
loop {
let (left, right) = slice.split_at_mut(i);
i = if let Some((pivot, right)) = right.split_first_mut() {
let mut left_iter = left.iter_mut().enumerate();
let mut right_iter = right.iter_mut().enumerate().rev();
loop {
if let Some((l, lele)) = left_iter.by_ref().find(|(_, ele)| ele > &pivot) {
if let Some((_, rele)) = right_iter.by_ref().find(|(_, ele)| ele < &pivot) {
std::mem::swap(lele, rele);
} else {
std::mem::swap(pivot, lele);
break l
}
} else {
if let Some((r, rele)) = right_iter.by_ref().find(|(_, ele)| ele < &pivot) {
std::mem::swap(pivot, rele);
break i + r
} else {
return Some((left, right))
}
}
}
} else {
return None
}
}
}
fn partition<T: Ord>(slice: &mut [T]) -> Option<(&mut [T], &mut [T])> {
let len = slice.len();
let pivot = len / 2;
_partition(slice, pivot)
}
fn quick_sort<T: Ord>(slice: &mut [T]) {
partition(slice).map(|(left, right)| {
quick_sort(left);
right.split_first_mut().map(|(_, right)| quick_sort(right))
});
}
Almost similar to the original but, here it will not do the splitting of slice again(playround).
Here it throws an error.
error[E0499]: cannot borrow `*slice` as mutable more than once at a time
--> src/main.rs:4:29
|
2 | fn _partition<T: Ord>(slice: &mut [T], mut i: usize) -> Option<(&mut [T], &mut [T])> {
| - let's call the lifetime of this reference `'1`
3 | loop {
4 | let (left, right) = slice.split_at_mut(i);
| ^^^^^^^^^^^^^^^^^^^^^ `*slice` was mutably borrowed here in the previous iteration of the loop
...
22 | return Some((left, right))
| ------------------- returning this value requires that `*slice` is borrowed for `'1`
I actually rewrote the _partition function in a recursive manner(here).
fn _partition<T: Ord>(slice: &mut [T], i: usize) -> Option<usize> {
let (left, right) = slice.split_at_mut(i);
let i = if let Some((pivot, right)) = right.split_first_mut() {
let mut left_iter = left.iter_mut().enumerate();
let mut right_iter = right.iter_mut().enumerate().rev();
loop {
if let Some((l, lele)) = left_iter.by_ref().find(|(_, ele)| ele > &pivot) {
if let Some((_, rele)) = right_iter.by_ref().find(|(_, ele)| ele < &pivot) {
std::mem::swap(lele, rele);
} else {
std::mem::swap(pivot, lele);
break l
}
} else {
if let Some((r, rele)) = right_iter.by_ref().find(|(_, ele)| ele < &pivot) {
std::mem::swap(pivot, rele);
break i + r
} else {
return Some(i)
}
}
}
} else {
return None
};
_partition(slice, i)
}
Here also two mutable borrows are happening. One at line 3: let (left, right) = slice.split_at_mut(i); and another at line 28:_partition(slice, i). But, it will not give an error. Only distinction from the second implementation is: there, it also returns the borrow return Some((left, right)) which needs to be alive as slice.
The problem here is: the compiler knows that if the function is already returning Some((left, right)) means the second borrow never occurs. If it is not returning anything means, the function is almost same the third implementation of the _partition function. Why does this has to be an error?
Is there anyway the code can be rearranged to the second implementation work? Or should I stick with first implementation?
Also on side note, why there is no fallible version of split_at_mut method? I checked in rust godbolt(here). There is panicking code also added.
I don't think it will ever fail this assumption(assertion failed: mid <= self.len()). But unfortunately, the rust compiler wasn't able to prove that.
The tests didn't fail tho.
Is there any way to remove that assert!(mid <= self.len()); in split_at_mut method?
It would've nicer if it had api like thisfn split_at_mut(&mut self, mid: usize) -> Option<(&mut [T], &mut [T])>. I mean split_first, split_last has Option as return but, why not this?