2
\$\begingroup\$

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);
}
```
\$\endgroup\$
  • \$\begingroup\$ (Positive you want to sort arrays of len 1 recursively?) \$\endgroup\$ – greybeard Feb 23 at 17:53
  • \$\begingroup\$ Oh, right, it would be better with if n > 1 ! Thanks @greybeard \$\endgroup\$ – Sebastien Feb 23 at 18:58
1
\$\begingroup\$

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
  1. Rename i_pivot to j, since it is just an index and your pivot is a[n - 1].

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

  3. 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);
}

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.