sorting_rs/
quick_sort.rs

1/// Sorts a slice in-place using
2/// [Quick sort](https://en.wikipedia.org/wiki/Quicksort), 
3/// [Dual-Pivot Quicksort](https://www.researchgate.net/publication/259264490_Dual_pivot_Quicksort)
4/// All kinds of slices can be sorted as long as they implement
5/// [`PartialOrd`](https://doc.rust-lang.org/std/cmp/trait.PartialOrd.html).
6/// Dual pivot quicksort additionally needs [`Copy`](https://doc.rust-lang.org/std/marker/trait.Copy.html)
7/// 
8/// Quicksort can be compared to merge sort as it also is a divide-and-conquer
9/// algorithm. However, quicksort does all the heavy work before the recursive
10/// calls, so it could also be called a conquer-and-divide algorithm. This
11/// implementation uses the
12/// [Lomuto partition scheme](https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme).
13///
14/// # Examples
15/// ```rust
16/// let mut vec = vec![0, -1, -2, -3,];
17/// sorting_rs::quick_sort(&mut vec);
18/// assert_eq!(vec, &[-3, -2, -1, 0]);
19/// ```
20/// ```rust
21/// let mut strings = vec!["rustc", "cargo", "rustup"];
22/// sorting_rs::quick_sort(&mut strings);
23/// assert_eq!(strings, &["cargo", "rustc", "rustup"]);
24/// ```
25/// ```rust
26/// let mut vec = vec![0, -1, -2, -3,];
27/// sorting_rs::quick_dual_sort(&mut vec);
28/// assert_eq!(vec, &[-3, -2, -1, 0]);
29/// ```
30/// ```rust
31/// let mut strings = vec!["rustc", "cargo", "rustup"];
32/// sorting_rs::quick_dual_sort(&mut strings);
33/// assert_eq!(strings, &["cargo", "rustc", "rustup"]);
34/// ```
35
36pub fn quick_sort<T: PartialOrd>(input: &mut [T]) {
37    if input.len() > 1 {
38        let pivot = lomuto_partition(input);
39        quick_sort(&mut input[..pivot]);
40        quick_sort(&mut input[pivot + 1..]);
41    }
42}
43
44/// Partitions a slice according to the Lomuto partition scheme.
45fn lomuto_partition<T: PartialOrd>(input: &mut [T]) -> usize {
46    let pivot = input.len() - 1;
47    let mut swap = 0;
48    for i in 0..pivot {
49        if input[i] < input[pivot] {
50            if swap != i {
51                input.swap(swap, i);
52            }
53            swap += 1;
54        }
55    }
56
57    if swap != pivot {
58        input.swap(swap, pivot);
59    }
60    swap
61}
62
63pub fn quick_dual_sort<T: PartialOrd + Copy>(input: &mut [T]) {
64    if input.len() < 2 {return;}
65    dual_pivot(input, 0, input.len() - 1);
66}
67
68fn dual_pivot<T: PartialOrd + Copy>(input: &mut [T], start: usize,
69end: usize) {
70    if start >= end {return;}
71    if input[start] > input[end] {
72        input.swap(start, end);
73    }
74    let lpivot = input[start];
75    let rpivot = input[end];
76
77    let mut startm = start + 1;
78    let mut endm = end - 1;
79
80    let mut point = startm;
81
82    while point <= endm {
83        if input[point] < lpivot {
84            input.swap(point, startm);
85            startm += 1;
86        }
87        else if input[point] >= rpivot {
88            while input[endm] > rpivot && point < endm {
89                endm -= 1;
90            }
91            input.swap(point, endm);
92
93            if input[point] < lpivot {
94                input.swap(point, startm);
95                startm += 1;
96            }
97        }
98        point += 1;
99    }
100    startm -= 1;
101    endm += 1;
102    input.swap(start, startm);
103    input.swap(end, endm);
104
105    dual_pivot(input, start, startm);
106    dual_pivot(input, startm + 1, endm);
107    dual_pivot(input, endm, end);
108}
109
110#[cfg(test)]
111mod tests {
112    use super::*;
113
114    #[test]
115    fn test_quick() {
116        let mut vector_in = vec![10, 20, 11, 24];
117        quick_sort(&mut vector_in);
118        debug_assert_eq!(vector_in, vec![10, 11, 20, 24]);
119    }
120    #[test]
121    fn test_quick_empty() {
122        let mut vector_in:Vec<i32> = vec![];
123        quick_sort(&mut vector_in);
124        debug_assert_eq!(vector_in, &[]);
125    }
126    #[test]
127    fn test_quick_len1() {
128        let mut vector_in = vec![1];
129        quick_sort(&mut vector_in);
130        debug_assert_eq!(vector_in, vec![1]);
131    }
132    #[test]
133    fn test_quick_dual() {
134        let mut vector_in = vec![10, 20, 11, 24];
135        quick_dual_sort(&mut vector_in);
136        debug_assert_eq!(vector_in, vec![10, 11, 20, 24]);
137    }
138    #[test]
139    fn test_quick_two_elem() {
140        let mut vector_in = [20, 10];
141        quick_dual_sort(&mut vector_in);
142        debug_assert_eq!(vector_in, [10, 20]);
143    }
144    #[test]
145    fn test_quick_dual_longer() {
146        let mut vector_in = [10, 20, 11, 24, 22, 21, 19];
147        quick_dual_sort(&mut vector_in);
148        debug_assert_eq!(vector_in, [10, 11, 19, 20, 21, 22, 24]);
149    }
150    #[test]
151    fn test_quick_dual_empty() {
152        let mut vector_in:Vec<i32> = vec![];
153        quick_dual_sort(&mut vector_in);
154        debug_assert_eq!(vector_in, &[]);
155    }
156    #[test]
157    fn test_quick_dual_len1() {
158        let mut vector_in = vec![1];
159        quick_dual_sort(&mut vector_in);
160        debug_assert_eq!(vector_in, vec![1]);
161    }
162}
sorting_rs/quick_sort.rs

sorting_rs/
quick_sort.rs
