Type problem with Usize and Index in a quicksort algorithm

user_16614170 0
Viewed 98

I am trying to implement the quicksort algorithm with rust, the problem is that, I have a var named 'i' which is used as an iterator, but at first, its value is '-1', and I cannot set it to a usize type because it is negative, but I also cannot set it to a isize type because isize types cannot be used as indices.

Partition function:

  fn partition(arr: &mut [isize], low: usize, high: usize) -> usize {
        let mut i: usize = low - 1; // when changed to isize, I do not encounter any errors but the algorithm itself doesnt work like it should.//
        let mut j: usize = low;
        let pivot: isize = arr[high];
        while j < high {
            if arr[j] <= pivot {
                i += 1;
                arr.swap(i, j);
            }
            j += 1;
        }
        arr.swap(i + 1, high);
        return i + 1;
    }

if I try to run the code above with another quicksort function, this is the error I get:

thread 'main' panicked at 'attempt to subtract with overflow', src\functions.rs:2:24
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
rust quicksort
2 Answers

There are of course many ways of solving this. The easiest is to let i start at low instead of low - 1, and increment i after swapping:

fn partition(arr: &mut [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;
}

This way, i can never be less than zero, while the code still does exactly the same thing.

(Note that I also used a for loop to lopp over the values for j. This change isn't really needed, but it makes the code easier to read.)

user_2796270

You can use casts to index with isize, since you know they never overflow. It also covers the full slice range, since slices cannot have more than isize::MAX elements:

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

For extra safety (at the expense of performance), you can use try_into():

fn partition(arr: &mut [isize], low: usize, high: usize) -> usize {
    let mut i = isize::try_from(low).unwrap() - 1;
    let mut j = low;
    let pivot = arr[high];
    while j < high {
        if arr[j] <= pivot {
            i += 1;
            arr.swap(i.try_into().unwrap(), j);
        }
        j += 1;
    }
    arr.swap((i + 1).try_into().unwrap(), high);
    return (i + 1).try_into().unwrap();
}

But I would not recommend walking this path, but rather, changing your code to use usize as noted in the answer by @SvenMarnach.

user_78843050
Related