Rust Code:
//todo: Quick Sort
pub fn quick_sort<T: Ord>(arr: &mut [T]) {
let len = arr.len();
if len > 1 {
_quick_sort(arr, 0, len - 1);
}
}
fn _quick_sort<T: Ord>(arr: &mut [T], mut lo: usize, mut hi: usize) {
while lo < hi {
let pivot = partition(arr, lo, hi);
if pivot - lo < hi - pivot {
if pivot > 0 {
_quick_sort(arr, lo, pivot - 1);
}
lo = pivot + 1;
} else {
_quick_sort(arr, pivot + 1, hi);
hi = pivot - 1;
}
}
}
pub fn partition<T: PartialOrd>(arr: &mut [T], lo: usize, hi: usize) -> usize {
let pivot = hi;
let mut i = lo;
let mut j = hi -1;
loop {
while arr[i] < arr[pivot] {
i += 1;
}
while j > 0 && arr[j] > arr[pivot] {
j -= 1;
}
if j ==0 || i >= j {
break;
} else if arr[i] == arr[j]{
i += 1;
j-=1;
} else {
arr.swap(i, j);
}
}
arr.swap(i, pivot);
i
}
fn main() {
// Test case 1: Sorting integers
let mut numbers = vec![10, 7, 3, 1, 9, 4, 2, 8, 6, 5];
println!("Before sorting: {:?}", numbers);
quick_sort(&mut numbers);
println!("After sorting: {:?}", numbers);
// Test case 2: Sorting an already sorted array
let mut sorted_numbers = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
println!("Before sorting: {:?}", sorted_numbers);
quick_sort(&mut sorted_numbers);
println!("After sorting: {:?}", sorted_numbers);
// Test case 3: Sorting an array with duplicate elements
let mut duplicates = vec![4, 5, 5, 3, 2, 4, 1, 3];
println!("Before sorting: {:?}", duplicates);
quick_sort(&mut duplicates);
println!("After sorting: {:?}", duplicates);
// Test case 4: Sorting strings
let mut words = vec!["apple", "orange", "banana", "grape", "cherry"];
println!("Before sorting: {:?}", words);
quick_sort(&mut words);
println!("After sorting: {:?}", words);
// Test case 5: Sorting an empty array
let mut empty: Vec<i32> = vec![];
println!("Before sorting: {:?}", empty);
quick_sort(&mut empty);
println!("After sorting: {:?}", empty);
// Test case 6: Sorting a single-element array
let mut single = vec![42];
println!("Before sorting: {:?}", single);
quick_sort(&mut single);
println!("After sorting: {:?}", single);
}