Quicksort algorithm implemented in Rust language, with an easy to remember partitioning function.

Intro

In this video, I've shown how you can implement a quicksort algorithm in rust language. In the book Introduction to algorithms by Thomas H. Cormen, I've found an alternative to the Hoare partitioning method. I've presented it as well on the whiteboard.

Quicksort idea

Quicksort is a sorting algorithm using the divide and conquer strategy.

The main idea is that we will pick an element in the array we'll call it pivot.
Next, we need to find where this element needs to be placed so that all left elements are less or equal and everything on the right is greater. This procedure is called partitioning.

Analysis

Time complexity of quicksort is O(nlogn) on average and O(n^2) worst case. Space complexity is O(logn) since quicksort calls itself on the order of log(n) times (in the average case, worst case number of calls is O(n)), at each recursive call a new stack frame of constant size must be allocated.

Quicksort in rust

pub fn quicksort<T: Ord>(arr: &mut [T]) {
    _quicksort(arr, 0, (arr.len() - 1) as isize);
}

fn _quicksort<T: Ord>(arr: &mut [T], left: isize, right: isize) {
    if left <= right {
        let partition_idx = partition(arr, 0, right);

        _quicksort(arr, left, partition_idx - 1);
        _quicksort(arr, partition_idx + 1, right);
    }
}

fn partition<T: Ord>(arr: &mut [T], left: isize, right: isize) -> isize {
    let pivot = right;
    let mut i: isize = left as isize - 1;

    for j in left..=right - 1 {
        if arr[j as usize] <= arr[pivot as usize] {
            i += 1;
            arr.swap(i as usize, j as usize);
        }
    }

    arr.swap((i + 1) as usize, pivot as usize);

    i + 1
}