tinystd/sort/
quick.rs

1// Licensed under the Apache License, Version 2.0 (the "License");
2// you may not use this file except in compliance with the License.
3// You may obtain a copy of the License at
4//
5//     http://www.apache.org/licenses/LICENSE-2.0
6//
7// Unless required by applicable law or agreed to in writing, software
8// distributed under the License is distributed on an "AS IS" BASIS,
9// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
10// See the License for the specific language governing permissions and
11// limitations under the License.
12
13//! [Quicksort][1]. Not bad.
14//! [1]: https://en.wikipedia.org/wiki/Quicksort
15use super::*;
16
17pub struct Quick;
18
19/// The well-known recursive sorting algorithm
20pub fn quicksort<T: Ord>(slice: &mut [T]) {
21    match slice.len() {
22        0 | 1 => return,
23        2 => {
24            if slice[0] > slice[1] {
25                slice.swap(0, 1);
26                return;
27            }
28        }
29        _ => (),
30    }
31
32    let (pivot, rest) = slice.split_first_mut().expect("slice must be non-empty");
33    let mut left = 0;
34    let mut right = rest.len() - 1;
35
36    while left <= right {
37        if &rest[left] <= pivot {
38            left += 1;
39        } else if &rest[right] > pivot {
40            if right == 0 {
41                break;
42            }
43            right -= 1;
44        } else {
45            rest.swap(left, right);
46            left += 1;
47            if right == 0 {
48                break;
49            };
50            right -= 1;
51        }
52    }
53
54    // set the pivot to it's correct location
55    let left = left + 1;
56    slice.swap(0, left - 1);
57
58    // recurse
59    let (left, right) = slice.split_at_mut(left - 1);
60    quicksort(left);
61    quicksort(&mut right[1..]);
62}
63
64impl Sorter for Quick {
65    fn sort<T>(&self, slice: &mut [T])
66    where
67        T: Ord,
68    {
69        quicksort(slice);
70    }
71}
72
73#[cfg(test)]
74mod tests {
75    use super::*;
76
77    #[test]
78    fn it_works() {
79        let mut items = vec![4, 2, 3, 1];
80        Quick.sort(&mut items);
81        assert_eq!(items, &[1, 2, 3, 4]);
82    }
83}
tinystd/sort/quick.rs

tinystd/sort/
quick.rs
