[Rust]クイックソート[覚書]

セミコロンレスでクイックソートを書いてみたいのだけれど、とりあえず普通にクイックソートを書いてみた覚書。

quicksort.rs

pub fn quicksort<T: Ord + Copy>(numbers: &mut [T]) {
    let last: usize = numbers.len() - 1;
    q_sort(numbers, 0, last);
}

fn q_sort<T: Ord + Copy>(numbers: &mut [T], left: usize, right: usize) {
    let pivot = numbers[left];
    let mut l = left;
    let mut r = right;
    while l < r {
        while (numbers[r] >= pivot) && (l < r) {
            r = r - 1;
        }
        if l != r {
            numbers[l] = numbers[r];
            l = l + 1;
        }
        while (numbers[l] <= pivot) && (l < r) {
            l = l + 1;
        }
        if l != r {
            numbers[r] = numbers[l];
            r = r - 1;
        }
    }
    numbers[l] = pivot;
    if left < l {
        q_sort(numbers, left, l - 1);
    } 
    if right > l {
        q_sort(numbers, l + 1, right);
    }
}

#[cfg(test)]
mod tests {
    use super::*; // 外の定義にアクセスするため use

    #[test]
    fn test_quicksort(){
        let mut numbers = [5, 3, 1, 6, 8, 4, 7, 2];
        quicksort(&mut numbers);
        assert_eq!([1, 2, 3, 4, 5, 6, 7, 8], numbers);
    }
}

参考: http://www.codereading.com/algo_and_ds/algo/quick_sort.html