Quick Sort in Rust

In this article, we have presented how to implement Quick Sort in Rust Programming Language. Quick Sort is one of the most efficient sorting algorithm with an average case Time Complexity of O(N logN).

To understand Quick Sort algorithm in depth, go through these two articles first:

Table of contents:

  1. Partition and Pivot Selection in Rust
  2. Quick Sort in Rust
  3. Complete Rust code for Quick Sort

Let us get started with Quick Sort in Rust.

Partition and Pivot Selection in Rust

Partition and Pivot Selection is the most important step in Quick Sort. This section splits the array into two parts where Quick Sort is applied recursively.

We are taking the last element as the pivot. So, given a vector / list of elements of data type i32 (integer 32 bits), the function partition will modify the list of elements such that:

  • The pivot is at its correct position as it should be in a sorted array
  • All elements before the pivot is less than the pivot but not necessarily sorted.
  • All elements after the pivot is greater than the pivot but not necessarily sorted.
  • The index of the pivot which is of data type usize in Rust is returned from this function.

Following is the implementation of Partition function in Rust:

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

    while j < len - 1 {
        if slice[j] <= pivot {
            slice.swap(i, j);
            i += 1;
        }
        j += 1;
    }

    slice.swap(i, len - 1);
}

Note:

  • The slice is mutable (mut) as it is being modified.
  • The return type is usize as it returns the index of pivot element.
  • pivot element is the last element of the slice. Arrays are 0 index in Rust.
  • i and j are control variable and hence, are mutable.
  • Elements in slice are swapped when needed.

This partition function takes O(N) time.

Quick Sort in Rust

Using the above Partition function, we split the array / slice into two parts:

  • Part before pivot
  • Part after pivot

Both parts are sorted recursively.

Following is the implementation of Quick Sort function in Rust using the partition function:

fn quick_sort(slice: &mut [i32]) {
    if !slice.is_empty() {
        let partition_index = partition(slice);
        let len = slice.len();

        quick_sort(&mut slice[0..partition_index]);
        quick_sort(&mut slice[partition_index + 1..len]);
        assert_sorted(slice);
    }
}

Note:

  • Nothing is returned by Quick Sort function. The slice is sorted directly.
  • The call to partition function takes the whole slice and returns the partition index (partition_index).
  • We check if the slice is sorted using assert_sorted() function. You can skip this function.

On average, the function quick_sort() is called O(logN) times while each call to the partition() function takes O(N) time. Hence, the overall time complexity is O(N logN).

Complete Rust code for Quick Sort

Following is the complete Rust code for Quick Sort which involves:

  • a function random_vector() to create a slice of N elements
  • a function run_benchmark() to create a input slice using random_vector(), run quick sort on it and then, check if the output slice is really sorted or not using assert_sorted().
  • assert_sorted() makes sure that two consequtive element vec[i] and vec[i+1] are in correct order that is vec[i] < vec[i+1].
  • main() function is defined where run_benchmark() is called for a sample run of Quick Sort.
fn run_benchmark(size: u32) {
    let mut vec = random_vector(size);

    quick_sort(&mut vec);
    assert_sorted(&vec);
}

fn quick_sort(slice: &mut [i32]) {
    if !slice.is_empty() {
        let partition_index = partition(slice);
        let len = slice.len();

        quick_sort(&mut slice[0..partition_index]);
        quick_sort(&mut slice[partition_index + 1..len]);
        assert_sorted(slice);
    }
}

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

    while j < len - 1 {
        if slice[j] <= pivot {
            slice.swap(i, j);
            i += 1;
        }
        j += 1;
    }

    slice.swap(i, len - 1);

    i
}

fn assert_sorted(slice: &[i32]) {
    for i in 1..slice.len() {
        assert!(slice[i - 1] <= slice[i])
    }
}

fn random_vector(size: u32) -> Vec<i32> {
    let mut slice: Vec<i32> = Vec::new();
    for _ in 0..size {
        slice.push(rand::random::<i32>());
    }
    slice
}

fn main() {
    run_benchmark(100);
}

This completes the Rust implementation of Quick Sort algorithm.

With this article at OpenGenus, you must have the complete idea of how to implement and test Quick Sort in Rust Programming Language.