0

I have a quicksort algorithm that works individually, but when I pass it into a function that runs the algorithm a lot of times (1 million times to be specific), I encounter that error:

thread 'main' panicked at 'attempt to subtract with overflow', src\quicksort.rs:17:30 note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

quicksort.rs:

fn partition(arr: &mut Vec<isize>, low: usize, high: usize) -> usize {

        let mut i: usize = low;
        let pivot: isize = arr[high];
        for j in low..high {
            if arr[j] <= pivot {
                arr.swap(i, j);
                i += 1;
            }
        }
        arr.swap(i, high);
        return i;
    }
    
    pub fn quick_sort(arr: &mut Vec<isize>, low: usize, high: usize) {
        if low < high {
            let pivot_index: usize = partition(arr, low, high);
            quick_sort(arr, low, pivot_index - 1);
            quick_sort(arr, pivot_index + 1, high);
        }
    }

What could be the reason for the overflow?

Nathace
  • 454
  • 3
  • 10
  • 1
    You can trigger this error with some simple input: `quick_sort(&mut vec![3, 2, 1], 0, 2)` – kmdreko Dec 18 '21 at 22:21
  • 3
    Subtract with overflow is really underflow. You have `pivot_index - 1` in your code - you need to make sure `pivot_index` isn't zero (since it's unsigned, subtract 1 would underflow). – Cruz Jean Dec 18 '21 at 23:36
  • 1
    @CruzJean Oh, I didn't notice that my pivot_index is unsigned and gets subtracted meaning that it might go negative and cause an underflow. I've added the check to make sure it won't happen. Thanks! – Nathace Dec 19 '21 at 02:17

0 Answers0