my friend and I wrote a quicksort algorithm, he did it in c++ and I wrote it in rust. His algorithm is 10x times faster than mine when we measure the time for it to run on worst or best case scenario, 100 times in different vector lengths.
I want to know how can I make my algorithm faster, and I can't find a lot of information online about implementing a quicksort online.
That's my quicksort algorithm:
fn partition(arr: &mut Vec<isize>, low: usize, high: usize) -> usize {
let mut i: usize = low;
let pivot: isize = arr[high];
for j in low..high {
if arr[j] <= pivot {
arr.swap(i, j);
i += 1;
}
}
arr.swap(i, high);
return i;
}
pub fn quick_sort(arr: &mut Vec<isize>, low: usize, high: usize) {
if low < high {
let pivot_index: usize = partition(arr, low, high);
if pivot_index != 0 {
quick_sort(arr, low, pivot_index - 1);
quick_sort(arr, pivot_index + 1, high);
}
}
}
My timing function that returns the time in nanoseconds:
use std::time::Instant;
pub fn timing(
original_arr: &mut Vec<isize>,
algo: fn(arr: &mut Vec<isize>, low: usize, high: usize),
) -> u128 {
let mut copy_arr: Vec<isize> = original_arr.to_vec();
let last_index = copy_arr.len() - 1;
let now = Instant::now();
algo(&mut copy_arr, 0, last_index);
let elapsed = now.elapsed();
return elapsed.as_nanos();
}