Quick sort implemented in Rust

Question

First attempt at writing Rust code. What do you think of the formatting? I think the type conversions are pretty messy. How can I make it more idiomatic?

fn quicksort(array: &mut[isize], first: usize, last: usize) {
 if first < last {
 let midpoint = partition(array, first, last);
 quicksort(array, first, midpoint - 1);
 quicksort(array, midpoint + 1, last);
 }
}
fn partition(array: &mut[isize], first: usize, last: usize) -> usize {
 let pivot = array[last];
 let i: isize = first as isize;
 let mut i: isize = i - 1;
 let mut j = first;
 while j < last - 1 {
 if array[j] < pivot {
 i = i + 1;
 let k: usize = i as usize;
 swap(array, k, j);
 }
 j = j + 1;
 }
 let k: isize = i + 1;
 let k: usize = k as usize;
 if array[last] < array[k] {
 swap(array, k, last);
 }
 return k;
}
fn swap(array: &mut[isize], a: usize, b: usize) {
 let temp = array[a];
 array[a] = array[b];
 array[b] = temp;
}
fn main() {
 let mut array = [3, 5, 1, 4, 2];
 quicksort(&mut array, 0, 4);
 println!("{:?}", array);
}

• ben rudgers: C.A.R Hoares' original paper Quicksort
• ben rudgers: This link will provide a token by clicking on the PDF link, academic.oup.com/comjnl/article/5/1/10/395338

Answer 1

1. Your implementation is incorrect. It fails for all sorts of inputs, but the simplest is

   let mut array = [0, 0];
   quicksort(&mut array, 0, 1);
   

2. Figuring out how to even call quicksort is overly complicated. Why do I have to pass in these numbers; can't the code figure that out?

3. Run rustfmt. It will automatically tell you things like:

   • &mut[T] should be written as &mut [T].

4. Run clippy. It will automatically tell you things like:

   • Not to use return at the end of a function.
   • That you can use a += b instead of a = a + b
   • That you've re-implemented slice::swap

---

Since the code doesn't work, I don't know that the transforms I made preserve the existing behavior. The rest is caveat emptor.

1. You have redundant type declarations. You don't need to say let x: T = y as T, just let x = y as T.

2. You also don't often need to specify the type at all, type inference can handle it.

3. Presumably you converted to an isize because you were subtracting one from zero. Instead, increase the values by one to keep it in the range of a usize. To transform, add one to the initial value of i and subtract one from the usages of i, then remove the casts and simplify the math.

fn partition(array: &mut [isize], first: usize, last: usize) -> usize {
 let pivot = array[last];
 let mut i = first;
 let mut j = first;
 while j < last - 1 {
 if array[j] < pivot {
 array.swap(i, j);
 i += 1;
 }
 j += 1;
 }
 if array[last] < array[i] {
 array.swap(i, last);
 }
 i
}