sort_algorithms/sort/
heapsort.rs

1#[cfg(test)]
2mod heapsort_test {
3
4    #[test]
5    fn sort() {
6        let mut arr = vec![7, 6, 5, 2, 4, 3, 1, 0, -1];
7        super::heapsort(&mut arr);
8        assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6, 7]);
9    }
10}
11
12/**
13Heap sort is an generalist algorithm that use the strategy order by selecion.
14# Examples
15
16```
17extern crate sort_algorithms;
18use sort_algorithms::heapsort;
19
20
21let mut arr = vec![7, 6, 5, 2, 4, 3, 1, 0];
22heapsort(&mut arr);
23assert_eq!(arr, [0, 1, 2, 3, 4, 5, 6, 7]);
24```
25*/
26
27pub fn heapsort<T>(arr: &mut [T])
28where
29    T: Copy + Clone + PartialEq + PartialOrd,
30{
31    let end = arr.len();
32    for start in (0..end / 2).rev() {
33        sift_down(arr, start, end - 1);
34    }
35
36    for end in (1..arr.len()).rev() {
37        arr.swap(end, 0);
38        sift_down(arr, 0, end - 1);
39    }
40}
41
42fn sift_down<T>(arr: &mut [T], start: usize, end: usize)
43where
44    T: Copy + Clone + PartialEq + PartialOrd,
45{
46    let mut root = start;
47    loop {
48        let mut child = root * 2 + 1;
49        if child > end {
50            break;
51        }
52
53        if child < end && arr[child] < arr[child + 1] {
54            child += 1;
55        }
56        if arr[root] < arr[child] {
57            arr.swap(root, child);
58            root = child;
59        } else {
60            break;
61        }
62    }
63}
sort_algorithms/sort/heapsort.rs

sort_algorithms/sort/
heapsort.rs
