competitive_programming_lib/Sorting/quick_sort.rs
1pub fn quick_sort(arr: &mut [i32]) {
2 if arr.len() <= 1 {
3 return;
4 }
5 let pivot_index = partition(arr);
6 let (left, right) = arr.split_at_mut(pivot_index);
7 quick_sort(left);
8 quick_sort(&mut right[1..]);
9}
10
11fn partition(arr: &mut [i32]) -> usize {
12 let pivot = arr.len() - 1;
13 let mut i = 0;
14 for j in 0..pivot {
15 if arr[j] < arr[pivot] {
16 arr.swap(i, j);
17 i += 1;
18 }
19 }
20 arr.swap(i, pivot);
21 i
22}