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.
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.
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
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
[ 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
, 1 views today
Got comments or suggestions?
We disabled the comments on this site to fight off spammers,
but you can still contact us via our
Facebook 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?