sorts/
shell_sort.rs

1struct GapSequence {
2    gap: usize,
3}
4
5impl GapSequence {
6    fn new(n: usize) -> Self {
7        Self { gap: n }
8    }
9}
10
11impl Iterator for GapSequence {
12    type Item = usize;
13
14    fn next(&mut self) -> Option<usize> {
15        self.gap /= 2;
16
17        if self.gap > 0 {
18            Some(self.gap)
19        } else {
20            None
21        }
22    }
23}
24
25pub fn shell_sort<T: PartialOrd>(s: &mut [T]) {
26    let len = s.len();
27    let gaps = GapSequence::new(len);
28
29    for gap in gaps {
30        for i in gap..len {
31            let mut j = i;
32
33            while j >= gap && s[j - gap] > s[j] {
34                s.swap(j - gap, j);
35
36                j -= gap;
37            }
38        }
39    }
40}
41
42#[cfg(test)]
43mod test {
44    use super::*;
45
46    #[test]
47    fn correct_gap_sequence() {
48        let gaps: Vec<_> = GapSequence::new(10).collect();
49        assert_eq!(gaps, &[5, 2, 1]);
50    }
51
52}
sorts/shell_sort.rs

sorts/
shell_sort.rs
