median_three_quicksort/
quicksort.rs

1///Taking three random index values determine a starting pivot.
2///Once the starting pivot is setup the initial partition is done
3///with the pivot location returned.
4///Using the pivot location begin with the left partition
5///and sort values in place. Once the left partition is sorted
6///then the right partition is sorted. Repeat until left is
7///greater than right.
8
9use uniq_vec;
10
11fn median_three<T: Ord>(vals: &mut [T]) {
12    //Instead of a median from left, right and middle
13    //this implementation picks three random indices and
14    //compares the values to find a median for use as the
15    //initial pivot value.
16    let rand_idx = uniq_vec::new_vec(3, 1, vals.len());
17
18    let median = 
19        if vals[rand_idx[0]] > vals[rand_idx[1]] &&
20        vals[rand_idx[0]] < vals[rand_idx[2]] {
21            rand_idx[0]
22        } else if vals[rand_idx[1]] > vals[rand_idx[0]] &&
23        vals[rand_idx[1]] < vals[rand_idx[2]] {
24            rand_idx[1]
25        } else {
26            rand_idx[2]
27        };
28
29    vals.swap(0, median);
30}
31
32
33fn partition<T: Ord>(array: &mut [T], left: usize, right: usize) -> usize{
34    //Move values to the left relative to the pivot value sorting the collection.
35    let mut pivot = left;
36
37    for i in left+1..right+1 {
38        if array[i] <= array[left] {
39            pivot += 1;
40            array.swap(i, pivot);
41        }
42    }
43    array.swap(pivot, left);
44
45    //If the vec starts with the lowest number in position 0 then the
46    //the first left pass _quicksort call after partition will fail due
47    //to an overflow caused by 0 - 1.
48
49    let pivot = match pivot {
50        0 => 1,
51        _ => pivot
52    };
53    pivot
54}
55
56fn _quicksort<T: Ord>(array: &mut [T], left: usize, right: usize) {
57    //Check if left is greater than right at which point the
58    //collection has been sorted in place.
59    if left >= right {
60        return
61    }
62
63    let pivot_position = partition(array, left, right);
64    _quicksort(array, left, pivot_position -1);
65    _quicksort(array, pivot_position + 1, right)
66}
67
68pub fn quicksort<T: Ord>(unsorted_vec: &mut [T]) {
69    //check vec length and return if not long enough to sort.
70    //consider how to change up to use references and no 
71
72    if unsorted_vec.len () <= 1 {
73        return
74    } else {
75        let right = unsorted_vec.len() - 1;
76        median_three(unsorted_vec);
77        _quicksort(unsorted_vec, 0, right);
78    }
79}
80
median_three_quicksort/quicksort.rs

median_three_quicksort/
quicksort.rs
