Quick sort algorithm in Rust

Question

I have written this Rust code to implement the quick sort algorithm. Could you review it and tell me if it is idiomatic or not? Especially about my use of the slices?

fn quick_sort<T: Ord>(array: &mut [T]) {
 let n = array.len();
 if n > 0 {
 let mut i_pivot = 0;
 for i in 1..n {
 if &array[i] < &array[n - 1] {
 array.swap(i, i_pivot);
 i_pivot += 1;
 }
 }
 array.swap(i_pivot, n - 1);
 quick_sort(&mut array[0..i_pivot]);
 quick_sort(&mut array[i_pivot + 1..n]);
 }
}
fn main() {
 // Fixed-size array (type signature is superfluous)
 let mut xs = [
 8, 13, 20, 13, 4, 21, 24, 13, 18, 23, 14, 6, 10, 2, 4, 6, 16, 6, 17, 9, 8, 20, 14, 19, 7,
 9, 18, 0, 18, 1, 8, 10,
 ];
 quick_sort(&mut xs);
 println!("{:?}", xs);
}
```

• greybeard: (Positive you want to sort arrays of len 1 recursively?)
• Sebastien: Oh, right, it would be better with if n > 1 ! Thanks @greybeard

Answer 1

Code review:
1. Your code has a bug here for i in 1..n,
the correct version starts from zero: for i in 0..n,
Change your main to the following code and then cargo run:

fn main() {
 let mut xs = vec![
 8, 13, 20, 13, 4, 21, 24, 13, 18, 23, 14, 6, 10, 2, 4, 6, 16, 6, 17, 9, 8, 20, 14, 19, 7,
 9, 18, 0, 18, 1, 8, 10,
 ];
 let mut v = xs.clone();
 v.sort();
 quick_sort(&mut xs);
 assert_eq!(v, xs);
}

You will see this error:

thread 'main' panicked at 'assertion failed: `(left == right)`
 left: `[0, 1, 2, 4, 4, 6, 6, 6, 7, 8, 8, 8, 9, 9, 10, 10, 13, 13, 13, 14, 14, 16, 17, 18, 18, 18, 19, 20, 20, 21, 23, 24]`,
 right: `[0, 1, 2, 4, 6, 6, 7, 6, 8, 4, 8, 9, 9, 10, 10, 8, 13, 13, 14, 14, 16, 17, 18, 18, 18, 19, 20, 20, 13, 23, 24, 21]`', src/main.rs:25:5

2. Rename i_pivot to j, since it is just an index and your pivot is a[n - 1].

3. Change if n > 0 to if n > 1 since the slice length should be at least two.

4. You don't need Ord here, PartialOrd is enough (try it here):

fn quick_sort<T: PartialOrd>(a: &mut [T]) {
 let n = a.len();
 if n > 1 {
 let mut j = 0;
 for i in 0..n {
 if &a[i] < &a[n - 1] {
 a.swap(i, j);
 j += 1;
 }
 }
 a.swap(j, n - 1); // pivot
 quick_sort(&mut a[0..j]);
 quick_sort(&mut a[j + 1..n]);
 }
}
fn main() {
 let mut xs = vec![
 8, 13, 20, 13, 4, 21, 24, 13, 18, 23, 14, 6, 10, 2, 4, 6, 16, 6, 17, 9, 8, 20, 14, 19, 7,
 9, 18, 0, 18, 1, 8, 10,
 ];
 let mut v = xs.clone();
 v.sort();
 quick_sort(&mut xs);
 assert_eq!(v, xs);
}