0
\$\begingroup\$

I have implemented the classical Hoare's algorithm, but I think that the implementation is not readable enough. I have tried to refactor it in the way that I used to use in C#. But now I have got compiler errors.

Let me show some details. This is the first implementation:

pub fn quicksort<T>(array: &mut Vec<T>) where T: Ord {
    partition(array, 0, array.len() as isize - 1);
}

fn partition<T>(array: &mut Vec<T>, start: isize, end: isize) where T: Ord {
    let length = end - start + 1;
    if length == 0 || length == 1 {
        return;
    }

    let mut left = start;
    let mut right = end;

    loop {
        let pivot = &array[start as usize];
        while array[left as usize] < *pivot {
            left += 1
        }

        while array[right as usize] > *pivot {
            right -= 1
        }

        if left < right {
            array.swap(left as usize, right as usize);
            left += 1;
            right -= 1;
        } else {
            break;
        }
    }

    partition(array, start, right);
    partition(array, right + 1, end);
}

It seems it works, at least my tests are passed.

fn main() {
    test_arrays(&mut vec![], &vec![]);
    test_arrays(&mut vec![1], &vec![1]);
    test_arrays(&mut vec![1, 2, 3, 4, 5], &vec![1, 2, 3, 4, 5]);
    test_arrays(&mut vec![5, 4, 3, 2, 1], &vec![1, 2, 3, 4, 5]);
    test_arrays(&mut vec![2, 3, 1, 5, 4], &vec![1, 2, 3, 4, 5]);
}

fn test_arrays(source: &mut Vec<i32>, target: &Vec<i32>) {
    quicksort(source);

    assert!(source.iter().eq(target.iter()));
}

Next are my questions. First, I would rather declare pivot as the variable, not the reference:

loop {
    let pivot = array[start as usize];
    while array[left as usize] < pivot {
        left += 1
    }

    while array[right as usize] > pivot {
        right -= 1
    }
. . .

But when I do it, I get the error:

   |
29 |         let pivot = array[start as usize];
   |                     ^^^^^^^^^^^^^^^^^^^^^
   |                     |
   |                     move occurs because value has type `T`, which does not implement the `Copy` trait
   |                     help: consider borrowing here: `&array[start as usize]`

I get what it means, but I don't want to limit the question with the Copy trait.

Next, I would rather move pivot's assignment out of the loop:

let pivot = &array[start as usize];

loop {
    while array[left as usize] < *pivot {
        left += 1
    }

    while array[right as usize] > *pivot {
        right -= 1
    }
. . .

When I do it, I get the another error:

error[E0502]: cannot borrow `*array` as mutable because it is also borrowed as immutable
  --> src\main.rs:39:13
   |
27 |     let pivot = &array[start as usize];
   |                  ----- immutable borrow occurs here
...
30 |         while array[left as usize] < *pivot {
   |                                      ------ immutable borrow later used here
...
39 |             array.swap(left as usize, right as usize);
   |             ^^^^^ mutable borrow occurs here

As I get, the compiler has protected me from the case when the pivot has changed after the swapping. But I don't like that the pivot is recalculated in every iteration of the loop although it keeps the same value in most cases.

I may keep the code with recalculation, or I may add the Copy trait.

Finally, I think that the partition function is too large. I want to extract the body of loop to the an another function. I can do it if I will add the Copy trait to the quicksort and partition implementations:

pub fn quicksort<T>(array: &mut Vec<T>) where T: Ord+Copy {
    partition(array, 0, array.len() as isize - 1);
}

fn partition<T>(array: &mut Vec<T>, start: isize, end: isize)
where T: Ord+Copy {
    let length = end - start + 1;
    if length == 0 || length == 1 {
        return;
    }

    let mut left = start;
    let mut right = end;

    loop {
        swap_next_unordered_elements(array, &mut left, &mut right, array[start as usize]);
        if left >= right {
            break;
        }
    }

    partition(array, start, right);
    partition(array, right + 1, end);
}

fn swap_next_unordered_elements<T>(array: &mut Vec<T>, left: &mut isize, right: &mut isize, pivot: T)
where T: Ord+Copy {
    while array[*left as usize] < pivot {
        *left += 1
    }

    while array[*right as usize] > pivot {
        *right -= 1
    }

    if *left < *right {
        array.swap(*left as usize, *right as usize);
        *left += 1;
        *right -= 1;
    }
}

As for me, this code looks simpler. Unfortunately, the quicksort has had the Copy trait that was not needed in the "complicated" version of the code.

So, what is the best solution? Should I keep the first ("complicated") version of the code without Copy? Or should I make simpler implementation with the Copy?

Or maybe there is another way to make simple generic quicksort?

\$\endgroup\$
7
  • \$\begingroup\$ Not sure if anyone but me is still paying attention to this 2 year old post, but I'm curious why you're storing the indices as isizes just to convert them to usizes when they're used for indexing into the vec. Also note that you can make these take &[T] instead of &Vec<T>, and still use it the same way at the call site, since &Vec<T> derefs to &[T]. That adds the flexibility that the caller can also pass a &Box<[T]> or a &[T; N]. \$\endgroup\$
    – embradley
    Commented Jul 9, 2023 at 22:48
  • \$\begingroup\$ @embradley, the end variable can have value -1, so it's isize. The start variable is isize for symmetry. Thank you for notice about &[T] and &Vec<T>. It's because I didn't know Rust good enough that time. \$\endgroup\$ Commented Jul 10, 2023 at 5:09
  • \$\begingroup\$ Am I right that the only way end can be -1 is if the given list is empty from the start? In that case, you could add if list.is_empty() { return } right before the first call to partition, and you’d then know that the arguments for partition are all non-negative. \$\endgroup\$
    – embradley
    Commented Jul 11, 2023 at 11:12
  • \$\begingroup\$ @embradley, Hi. That's the place: if *left < *right { array.swap(*left as usize, *right as usize); *left += 1; *right -= 1; // *right can become -1 here } ``` \$\endgroup\$ Commented Jul 11, 2023 at 11:59
  • \$\begingroup\$ @embradley, current version of the code is placed here. \$\endgroup\$ Commented Jul 11, 2023 at 12:01

1 Answer 1

1
\$\begingroup\$

When you start using references and arrays in rust you tend to run into difficulties with the borrow checker. The borrow checker isn't smart enough to understand the invariants of the algorithm, and thus has to be overly cautious.

There are three solutions:

Use Indexes

In this approach, you simply never take a reference, always pass around an index. So instead of:

let pivot = array[start as usize];
while array[left as usize] < pivot {
    left += 1
}

while array[right as usize] > pivot {
    right -= 1
}

You would do:

let pivot = start as usize;
while array[left as usize] < array[pivot] {
    left += 1
}

while array[right as usize] > array[pivot] {
    right -= 1
}

If you follow this approach consistently, you'll find that borrow checker is happy. However, it does mean re-evaluating array[pivot] and similar a lot. After optimizations are applied, this isn't as big a deal as you might think.

Split Slices

Slices, and by extension Vec, have methods that you split it into distinct slices.

For example, you can do

 let (pivot, rest) = array.split_first_mut().unwrap();

Now you have independent references to the partition and the rest of the array. The borrow will understand that mutations to rest can't affect the pivot.

This is also a split_at_mut that splits at particular index you can use to divide a slice into two slices, perhaps to sort each independently.

Use Unsafe

You can use the unsafe function as_mut_ptr to get a pointer to the vec contents, and then use pointer logic to implement the algorithm with the borrow checker watching over your shoulder. Generally, its not worth doing this, but for some low level code it can make sense. You can also use get_unchecked to access the elements of the array without an index.

If you look at the code used in the standard libraries implementation of quicksort, it uses some combination of all three.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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