ford_johnson/
lib.rs

1#[cfg(test)]
2#[macro_use]
3extern crate quickcheck_macros;
4
5use std::cmp::Ordering;
6use std::collections::HashMap;
7
8/// Sort a slice of `usize` based on an explicit comparator.
9/// Usually used to perform an indirect sort (i.e., to compute the indices
10/// that would sort the given items).
11pub fn sort<F>(xs: &mut [usize], cmp: &mut F)
12where
13    F: FnMut(usize, usize) -> Ordering + Sized,
14{
15    if xs.len() < 2 {
16        return;
17    }
18
19    // First, swap all the largest elements to the front.
20    let mut partner: HashMap<usize, Vec<usize>> = HashMap::new();
21    let half = xs.len() / 2;
22    for i in 0..half {
23        if cmp(xs[i], xs[i + half]) == Ordering::Less {
24            xs.swap(i, i + half);
25        }
26        partner.entry(xs[i]).or_default().push(xs[i + half]);
27    }
28
29    // Now recursively sort those larger elements.
30    sort(&mut xs[..half], cmp);
31
32    // Now do an insertion-sort to get the latter half of the array into order.
33    for i in 0..half {
34        // Every step of the way we'll be inserting an extra element,
35        // so `x[i]` will be located at `xs[2*i]`.
36        let y = partner.get_mut(&xs[2 * i]).unwrap().pop().unwrap();
37        // We known that y[i] < x[i], so we need to insert it to the left of x[i].
38        let idx = find_insert_point(y, &xs[..2 * i], cmp);
39        // Make room.
40        xs[idx..half + i + 1].rotate_right(1);
41        // Insert it.
42        xs[idx] = y;
43    }
44    if xs.len() % 2 > 0 {
45        let i = xs.len() - 1;
46        let idx = find_insert_point(xs[i], &xs[..i], cmp);
47        xs[idx..].rotate_right(1);
48    }
49}
50
51fn find_insert_point<F>(x: usize, xs: &[usize], cmp: &mut F) -> usize
52where
53    F: FnMut(usize, usize) -> Ordering + Sized,
54{
55    let mut lo = 0;
56    let mut hi = xs.len();
57    while hi > lo {
58        let mid = lo + (hi - lo) / 2;
59        match cmp(x, xs[mid]) {
60            Ordering::Equal => return mid,
61            Ordering::Less => hi = mid,
62            Ordering::Greater => lo = mid + 1,
63        };
64    }
65    lo
66}
67
68#[cfg(test)]
69mod test {
70    use super::*;
71    use rand::seq::SliceRandom;
72    use rand::SeedableRng;
73
74    #[test]
75    fn sorts_correctly_smoke() {
76        let mut xs = vec![3, 5, 1, 2, 4];
77        sort(&mut xs, &mut |a, b| a.cmp(&b));
78        assert_eq!(xs, vec![1, 2, 3, 4, 5]);
79    }
80
81    #[test]
82    fn sorts_correctly_random() {
83        let init: Vec<usize> = (0..100).collect();
84        let mut prng = rand_pcg::Pcg32::seed_from_u64(42);
85        for _ in 0..1000 {
86            let mut xs = init.clone();
87            xs.shuffle(&mut prng);
88            sort(&mut xs, &mut |a, b| a.cmp(&b));
89            assert_eq!(xs, init);
90        }
91    }
92
93    #[test]
94    fn manual() {
95        let mut xs: Vec<usize> = (0..8).collect();
96        sort(&mut xs, &mut |a: usize, b: usize| {
97            println!("cmp {} vs {}", a, b);
98            a.cmp(&b)
99        });
100    }
101
102    fn count_cmps(mut xs: Vec<usize>) -> usize {
103        let mut cnt = 0;
104        sort(&mut xs, &mut |a: usize, b: usize| {
105            cnt += 1;
106            a.cmp(&b)
107        });
108        cnt
109    }
110
111    #[test]
112    fn right_number_of_comparisons_smoke() {
113        assert_eq!(count_cmps(vec![3, 5, 1, 2, 4]), 7);
114    }
115
116    #[test]
117    fn right_number_of_comparisons_eois() {
118        // From the Online Encyclopedia of Integer Sequences: https://oeis.org/A001768
119        let expected = vec![
120            0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 71, 76,
121            81, 86, 91, 96, 101, 106, 111, 116, 121, 126, 131, 136, 141, 146, 151, 156, 161, 166,
122            171, 177, 183, 189, 195, 201, 207, 213, 219, 225, 231, 237, 243, 249, 255,
123        ];
124        for (i, n) in expected.into_iter().enumerate() {
125            let a = count_cmps((0..i + 1).collect());
126            assert!(
127                a <= n,
128                "{} items can be sorted in {} cmps but we used {}",
129                i + 1,
130                n,
131                a
132            );
133        }
134    }
135
136    #[test]
137    fn right_number_of_comparisons_big() {
138        let mut xs: Vec<usize> = (0..100).collect();
139        let mut prng = rand_pcg::Pcg32::seed_from_u64(999);
140        xs.shuffle(&mut prng);
141        assert_eq!(count_cmps(xs), 530);
142    }
143
144    #[quickcheck]
145    fn sorts_correctly(xs: Vec<usize>) -> bool {
146        let mut ys = xs.clone();
147        let mut zs = xs.clone();
148        sort(&mut ys, &mut |a, b| a.cmp(&b));
149        zs.sort();
150        ys == zs
151    }
152}
ford_johnson/lib.rs

ford_johnson/
lib.rs
