Problem

We need to sort a provided vector vec using Quicksort algorithm. It is a commonly used divide and conquer sorting algorithm that on average has O(n log n) time complexity.

Example 1:

Input: vec = [-4, 1, 25, 50, 8, 10, 23]
Output: [-4, 1, 8, 10, 23, 25, 50]

Example 2:

Input: vec = [2, 1, 6, 10, 4, 1, 3, 9, 7]
Output: [1, 1, 2, 3, 4, 6, 7, 9, 10]

Solution

fn quick_sort(vec: &mut Vec<i32>) -> &Vec<i32> {

    fn partition(slice: &mut [i32]) -> usize {
        let pivot_idx = slice.len() - 1;
        let pivot = slice[pivot_idx];
        let mut next_swap_idx = 0;

        (0..slice.len()).for_each(|idx| {
            if slice[idx] < pivot {
                slice.swap(next_swap_idx, idx);
                next_swap_idx += 1;
            }
        });
        slice.swap(pivot_idx, next_swap_idx);

        next_swap_idx
    }

    fn qsort(slice: &mut [i32]) {
        let pivot_idx = partition(slice);
        let len = slice.len();
        if pivot_idx > 0 {
            qsort(&mut slice[0..pivot_idx]);
        }
        if pivot_idx < len - 1 {
            qsort(&mut slice[pivot_idx + 1..len]);
        }
    }

    if !vec.is_empty() {
        qsort(&mut vec[..]);
    }

    vec
}

Explanation

Usually Quicksort is implemented using 2 functions: a partition function and a recursive qsort function. The qsort function initially takes the original full slice of data (&mut vec[..]) based on the provided vector vec. Then it uses partition function call to partition the slice in-place around the selected pivot element and gets the pivot index as a result. The partitioning means that all elements less than the pivot are moved to the left of the pivot, and all elements greater than the pivot are moved to the right of the pivot. And then qsort function calls itself recursively for those 2 parts (for the left part and for the right part) until resulting parts are empty.

Step-by-step walk-through

Let's go through the process step-by-step using our sample input: vec = [-4, 1, 25, 50, 8, 10, 23].

When qsort is called for the first time, it gets the whole slice [-4, 1, 25, 50, 8, 10, 23] to work with. When we call partition, the slice is re-partitioned to be [-4, 1, 8, 10, 23, 50, 25]. The element 23 was selected as the pivot (in our implementation we select the last element as a pivot, but in other implementations it could be e.g. the first element, the middle element, or a random one). The partition function moved all elements less than 23 to the left of the pivot and greater elements to the right of the pivot, and returned the pivot index pivot_idx = 4.

Now qsort function calls itself recursively for each of those 2 parts (left and right): [-4, 1, 8, 10] and [50, 25].

• When the partition function is called for [-4, 1, 8, 10], it partitions the slice to be [-4, 1, 8, 10] and returns pivot_idx = 3 (no changes in the slice because 10 was selected as the pivot, and the elements less than the pivot were already left to the pivot).
  • The qsort is called for the left [-4, 1, 8] part again (and it is not called for the right part because it is empty). When the partition function is called for [-4, 1, 8], it partitions the slice to be [-4, 1, 8] and returns pivot_idx = 2 (no changes in the slice because 8 was selected as the pivot, and the elements less than the pivot were already left to the pivot).
    • The qsort is called for the left [-4, 1] part again (and it is not called for the right part because it is empty). When the partition function is called for [-4, 1], it partitions the slice to be [-4, 1] and returns pivot_idx = 1 (no changes in the slice because 1 was selected as the pivot, and the element less than the pivot was already left to the pivot).
      • The qsort is called for the left [-4] part again (and not called for the right part because it is empty). When the partition function is called for [-4], it obviously returns the same slice and pivot_idx = 0. The qsort would not be called again because all parts are exhausted.
• When the partition function is called for [50, 25], it partitions the slice to be [25, 50] and returns pivot_idx = 0. The element 25 was selected as the pivot and the other element was moved to the right of it because it was greater.
  • The qsort is called for the right [50] part again (and is not called for the left part because it is empty). When the partition function is called for 50, it obviously returns the same slice and pivot_idx = 0. The qsort would not be called again because all parts are exhausted.

Thus, at the end of the run we end up having the ordered vector [-4, 1, 8, 10, 23, 25, 50].

Complexity

The average time complexity of this solution is O(n log n) (n is a size of the input vector). The worst-case auxiliary space complexity is O(n) to reflect possible n nested recursive calls.

---

Rust Playground with this code