クイックソートのRustでの実装

quicksort.rs

use std::io::*;
use std::str::*;

fn read<T: FromStr>(s: &mut StdinLock) -> Option<T> {
    let s = s.by_ref().bytes().map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

fn main() {
    let s = stdin();
    let mut s = s.lock();
    let s = &mut s; // mutの参照にすることで何回使ってもOK
    let n: usize = read(s).unwrap();
    let mut num_vec: Vec<i32> = Vec::with_capacity(n);
    
    for _ in 0..n {
        let a: i32 = read(s).unwrap();
        num_vec.push(a);
    }
    quick_sort(&mut num_vec, 0, n-1);

    for a in &num_vec {
        print!("{} ", *a);
    }
    
}

fn quick_sort<T: PartialOrd>(v: &mut Vec<T>, p: usize, r: usize) {

    if p < r {
        let q = partition(v, p, r);
        quick_sort(v, p, q);
        quick_sort(v, q+1, r);
    }
}

fn partition<T: PartialOrd>(v: &mut Vec<T>, p: usize, r: usize) -> usize {

    let mut i = p as i32 - 1;
    let mut j = r as i32 + 1;

    loop {
        while { j -= 1; v[j as usize] > v[p] } {}
        while { i += 1; v[i as usize] < v[p] } {}
        if i < j {
            // rustだと入れ替えをちょっと頑張る。unsafeでやってもいいけど
            // let p1: *mut T = &mut v[i as usize];
            // let p2: *mut T = &mut v[j as usize];
            // unsafe {
            //     p1.swap(p2);
            // }
            let (v1, v2) = v.split_at_mut(j as usize); // [0,j)と[j, v.len())に分ける
            std::mem::swap(&mut v1[i as usize], &mut v2[0]);
        } else {
            return j as usize;
        }
    }
}