Quick Sort Algorithm in Rust

1. Introduction

QuickSort is a highly efficient sorting algorithm that employs a divide-and-conquer strategy. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. Its average-case time complexity is O(n log n) with the worst-case of O(n^2), although this worst-case scenario can often be avoided with a good choice of pivot selection strategies.

2. Implementation Steps

1. Choose a 'pivot' from the array.

2. Partition the array around the pivot, such that elements less than the pivot come before and elements greater than the pivot come after it.

3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

4. The base case of the recursion is arrays of size zero or one, which are always sorted.

3. Implementation in Rust Programming

fn quick_sort<T: Ord>(arr: &mut [T]) {
    if arr.len() <= 1 {
        return;
    }
    let pivot_index = partition(arr);
    quick_sort(&mut arr[0..pivot_index]);
    quick_sort(&mut arr[pivot_index + 1..]);
}
fn partition<T: Ord>(arr: &mut [T]) -> usize {
    let pivot = arr.last().unwrap().clone();
    let mut i = 0;
    for j in 0..arr.len() - 1 {
        if arr[j] <= pivot {
            arr.swap(i, j);
            i += 1;
        }
    }
    arr.swap(i, arr.len() - 1);
    i
}
fn main() {
    let mut numbers = [10, 7, 8, 9, 1, 5];
    quick_sort(&mut numbers);
    println!("{:?}", numbers);  // Prints: [1, 5, 7, 8, 9, 10]
}

Output:

[1, 5, 7, 8, 9, 10]

Explanation:

1. The main function quick_sort checks if the array has 1 or 0 elements (already sorted) and then proceeds with the sorting.

2. The partition function selects the last element as the pivot, places all smaller elements than the pivot before it and all greater elements after it. It returns the pivot's position.

3. In the quick_sort function, after partitioning the array, it recursively sorts the elements before and after the pivot.

4. The swap function in Rust's standard library is used to swap the elements of the array.

5. The main function provides a sample array and prints the sorted array.