i think i have written a right code that shouldn't panics, but it did. Why it happens?
And here's a interest thing: if u don't start with index 0 such as 1, it will work! Why??
pub struct Solution;
impl Solution {
pub fn sort_array(mut nums: Vec<i32>) -> Vec<i32> {
let r = nums.len() - 1;
// here, if u start with 1, it would not panic, and sort the array except the fist one
Self::quick_sort(&mut nums, 0, r);
nums
}
fn quick_sort(v: &mut [i32], l: usize, r: usize) {
if l >= r {
return;
}
let (mut left, mut right) = (l, r);
let pivot = v[left];
while left < right {
while left < right && v[right] >= pivot {
right -= 1
}
if v[right] < pivot {
v[left] = v[right]
}
while left < right && v[left] <= pivot {
left += 1
}
if v[left] > pivot {
v[right] = v[left]
}
}
if left >= right {
v[left] = pivot
}
Self::quick_sort(v, l, right - 1);
Self::quick_sort(v, right + 1, r);
}
}
The first thing I do when troubleshooting a panic is to dead through the backtrace and see which functions were being called when the panic occurs.
That usually points you towards the immediate error, and from there you can work backwards to figure out why (for example) an index you generated might be out of bounds.
The problem occurs in a call to quick_sort(&mut [0, 1, 1, 2, 0, 5], 0, 4), and the reported panic is attempt to subtract with overflow on line 35:
Self::quick_sort(v, l, right - 1);
There’s only one subtraction here, so the problem is likely to be that right is equal to zero— Subtracting 1 would then need to produce a -1_usize, which isn’t possible.
With this theory in hand, we can hand-execute the problematic call to see what’s going on. The pivot value is selected to be 0, which is the minimum value of the sublist being sorted. That means that this loop takes right to index 0, which then causes the problem.
while left < right && v[right] >= pivot {
right -= 1
}
It looks like you anticipated this problem somewhat because there’s an early exit at the top of the function when l >= r, but execution never gets there in this case because your r went outside of usize’s range.
It’s been quite a while since I looked at the quicksort algorithm so I thought I’d see what I could do with it in Rust; here’s my version:
fn quick_sort<T: Ord>(v: &mut [T]) {
if v.len() < 2 {
return;
}
// Pick the middle element as pivot, to de-pessimize sorted lists
v.swap(0, v.len()/2);
let [pivot, parts @ ..] = v else {
unreachable!()
};
let (mut left, mut right) = (0, parts.len());
loop {
match &mut parts[left..right] {
// Cursors have met; everything has been partitioned
[] => break,
// Move cursors past items that are already in the correct partition
[x, ..] if x < pivot => {
left += 1;
}
[.., y] if y >= pivot => {
right -= 1;
}
// Both cursors stopped, so both `x` and `y` need to be in the other partition
[x, .., y] => {
mem::swap(x, y);
}
// One of the two cursors must have already claimed the last item
[_] => unreachable!()
}
}
// Place pivot between partitions
v.swap(0, left);
Self::quick_sort(&mut v[..left]);
Self::quick_sort(&mut v[left+1..]);
}
}
Note that this will panic in debug if you sort_array(vec![]).
Things like this are why I would always suggest that you use half-open ranges, rather than the inclusive range that you're using here. (Like how .. in rust gives a half-open range.)
Notably, the "obvious" empty range for closed ranges is -1..=0, but you can't have that with usize. Having a range shrink down to end at 0..0 usually works better.
This is why Rust is so great.
Perhaps in some other language (not mentioning names) your code would have compiled and run without error. Perhaps the results were not quite right. I had this kind of problem with a Fourier Transform I originally wrote in C.