This post is about an example of the Quicksort algorithm in Rust.
Functions for Quicksort Algorithm Codes
Our example uses 3 functions – swap, partition, and quick_sort.
The Swap Function
The swap function exchanges the values between 2 elements in an array.
1 2 3 4 5 | fn swap(param_int_array: &mut [i32], i: usize, j: usize ) { let temp = param_int_array[i]; param_int_array[i] = param_int_array[j]; param_int_array[j] = temp; } |
The Partition Function
This Rust function picks a pivot index of an array or subarray. The quick_sort function uses that index to further break down the array at each recursion.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | fn partition(param_int_array: &mut [i32], start: usize, end: usize ) -> i32 { let mut pivot = param_int_array[end]; let mut index = start; let mut i = start; while i < end { if param_int_array[i] < pivot { swap(param_int_array, i, index); index+=1; } i+=1; } swap(param_int_array, index, end); return index as i32; } |
The quick_sort Function
These are the key Rust codes and the function is recursive. It uses the swap and partition functions.
1 2 3 4 5 6 7 8 9 10 | fn quick_sort(param_int_array: &mut [i32], start: usize, end: usize) { if start >= end { return; } let pivot = partition(param_int_array, start, end); println!("=={}", pivot); quick_sort(param_int_array, start, (pivot - 1) as usize); quick_sort(param_int_array, (pivot + 1) as usize, end); } |
Algorithm Demo Example
1 2 3 4 5 6 | fn main() { let mut int_values_array:[i32; 13] = [1, 0, 9, 8, 100, 345, 5, 6,7 , 4, 3, 2, 1]; let last_index = int_values_array.len() - 1; quick_sort(&mut int_values_array, 0, last_index); println!("{:?}", int_values_array) } |
Output
1 | [0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 100, 345] |
Tested with Rust 1.38.0.
Other Algorithms in Rust
For more algorithms in Rust, please go to Algorithms In Codes page
if i want use something like: = (0..1000).map(|_| rng.gen_range(10, 100)).collect();
let mut int_values_array: Vec
What should i change?