# Rust Interview Puzzles: Quicksort implementation

·

### 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.