Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #![allow(dead_code)]
- use rand::RngCore;
- #[derive(Copy, Clone)]
- enum PivotChoice {
- Random,
- Last,
- }
- fn main() {
- let mut numbers = [10, 8, 3, 6, 1, 4, 2, 5, 9, 7];
- let length = numbers.len();
- println!("{:?}", numbers);
- quick_sort(&mut numbers, 0, length, PivotChoice::Last);
- }
- fn quick_sort(mut array: &mut [i32], from: usize, to: usize, pc: PivotChoice) {
- fn partition(array: &mut [i32], from: usize, pivot_idx: usize, to: usize)
- -> usize {
- let pivot = array[pivot_idx];
- let num_left = array[from..to].iter().filter(|n| **n <= pivot).count()-1;
- let new_pivot_idx = from + num_left;
- array.swap(pivot_idx, new_pivot_idx);
- // l and r are indices for the left and right side respectively
- let mut r = to - 1;
- for l in from..new_pivot_idx {
- if array[l] > pivot {
- while array[r] > pivot {
- r -= 1;
- }
- array.swap(l, r);
- }
- }
- new_pivot_idx
- }
- if array[from..to].len() >= 2 {
- let pivot = match pc {
- PivotChoice::Random => rand::thread_rng().next_u32() as usize
- % (to - from) + from,
- PivotChoice::Last => to - 1,
- };
- let middle = partition(&mut array, from, pivot, to);
- print_progress(array, from, to);
- quick_sort(&mut array, from, middle, pc);
- quick_sort(&mut array, middle + 1, to, pc);
- }
- }
- // Print array with the region [from..to] highlighted in LaTeX format.
- fn print_progress(array: &mut [i32], from: usize, to: usize) {
- print!("[");
- for i in 0..from {
- print!("{}, ", array[i]);
- }
- print!("\\textcolor{{red}}{{");
- for i in from..to {
- print!("{}, ", array[i]);
- }
- print!("}}");
- for i in to..array.len() {
- print!("{}, ", array[i]);
- }
- println!("]");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement