algods/sort/
quick_sort.rs

1#[cfg(test)]
2mod unit_test;
3use rand::seq::SliceRandom;
4use rand::thread_rng;
5use std::cmp::Ordering;
6use std::mem::replace;
7
8/// Implementation of quick sort algorithm
9#[derive(Debug)]
10pub struct QuickSort<T> {
11    vec: Vec<T>,
12    // QuickSort is unstable in the sense that
13    // items with equal keys can be exchanged ?
14}
15
16impl<T: Ord + Clone> QuickSort<T> {
17    /// Creates a new quick sort instance from a `Vec`.
18    /// ```
19    /// use algods::sort::QuickSort;
20    /// let ms = QuickSort::init(vec![100, 20, 9, 17]);
21    /// ```
22    pub fn init(v: Vec<T>) -> Self {
23        Self { vec: v }
24    }
25
26    fn partition(&mut self, low: usize, high: usize) -> usize {
27        // Finds a partitioning index j, i.e such that elements at the left of index j
28        // are no greater than element j and elements at the right of index j are no larger
29        // than element j.
30        // run time complexity O(N)
31        let mut i = low + 1;
32        let mut j = high;
33        loop {
34            // find item on left to swap
35            while self.vec[i] <= self.vec[low] {
36                i += 1;
37                if i >= high {
38                    break;
39                }
40            }
41            // find item on right to swap
42            while self.vec[low] <= self.vec[j] {
43                j -= 1;
44                if j <= low {
45                    break;
46                }
47            }
48            // check if positions/pointers cross
49            if i >= j {
50                break;
51            }
52            // exchange i^th and j^th object to respect partitioning
53            let n = self.vec[j].clone();
54            self.vec[j] = replace(&mut self.vec[i], n);
55        }
56        // swap with partitioning item
57        let n = self.vec[j].clone();
58        self.vec[j] = replace(&mut self.vec[low], n);
59        j
60    }
61
62    fn sort(&mut self) {
63        // shuffle garantees performance ?
64        let mut rng = thread_rng();
65        self.vec.shuffle(&mut rng);
66        self.recursive_sort(0, self.vec.len() - 1);
67    }
68
69    fn recursive_sort(&mut self, low: usize, high: usize) {
70        if high <= low {
71            return;
72        }
73        let j: usize = self.partition(low, high);
74        if j >= 1 && j < self.vec.len() - 1 {
75            self.recursive_sort(low, j - 1);
76            self.recursive_sort(j + 1, high);
77        } else if j == 0 {
78            self.recursive_sort(j + 1, high);
79        } else {
80            self.recursive_sort(low, j - 1);
81        }
82    }
83
84    /// Sorts a `Vec` using quick sort algorithm. It moves the QuickSort.
85    /// ```
86    /// use algods::sort::QuickSort;
87    /// let mut v = vec![100, 20, 9, 17];
88    /// let qs = QuickSort::init(v.clone());
89    /// v.sort_unstable();
90    /// assert_eq!(qs.into_sorted_vec(), v);
91    /// ```   
92    pub fn into_sorted_vec(mut self) -> Vec<T> {
93        self.sort();
94        self.vec
95    }
96
97    /// Selects the kth largest element in the `Vec` instantiating the QuickSort using the
98    /// quick select algorithm
99    /// ```
100    /// use algods::sort::QuickSort;
101    /// let mut qs = QuickSort::init(vec![30, 13, 90, 50, 47, 100]);
102    /// assert_eq!(qs.select(3), 50);
103    /// ```
104    pub fn select(&mut self, k: usize) -> T {
105        // Selects the k^th largest element in self.vec (quick select algorithm)
106        // in linear time on average for median (k = N/2)
107        let mut rng = thread_rng();
108        self.vec.shuffle(&mut rng);
109        let mut low = 0;
110        let mut high = self.vec.len() - 1;
111        while high > low {
112            let j = self.partition(low, high);
113            match j.cmp(&k) {
114                // the k^th largest is on the right of element j
115                Ordering::Less => low = j + 1,
116                // the k^th largest is on the left of element j
117                Ordering::Greater => high = j - 1,
118                // j = k, we are done
119                Ordering::Equal => return self.vec[k].clone(),
120            }
121        }
122        self.vec[k].clone()
123    }
124}
algods/sort/quick_sort.rs

algods/sort/
quick_sort.rs
