4
\$\begingroup\$

The tests are taken from this answer on an insertion sort in rust question.

The algorithm is taken from Algorithms in a Nutshell (2nd Edition).

I'm not looking at crazy performance, the goal being to learn about basic algorithms and rust, but if there is something shockingly inefficient please let me know.

fn main() {}

fn heapify<T>(slice: &mut [T], idx: usize, max: usize)
    where T: Ord
{
    let mut largest = idx;
    let left = idx*2 + 1;
    let right = idx*2 + 2;

    if left < max && slice[left] > slice[largest] {
        largest = left;
    }

    if right < max && slice[right] > slice[largest] {
        largest = right;
    }

    if largest != idx {
        slice.swap(largest, idx);
        heapify(slice, largest, max);
    }
}

fn heap_sort<T>(slice: &mut [T])
    where T: Ord
{
    let len = slice.len();
    if len <= 1 {
        return;
    }
    for i in (0..len/2).rev() {
        heapify(slice, i, len);
    }
    for i in (1..len).rev() {
        slice.swap(0, i);
        heapify(slice, 0, i);
    }
}

#[macro_use]
extern crate quickcheck;

#[test]
fn test_heapify() {
    let mut values = [8, 11, 9, 2, 10, 16];
    heapify(&mut values, 2, 6);
    assert_eq!(values, [8, 11, 16, 2, 10, 9]);
    heapify(&mut values, 1, 6);
    assert_eq!(values, [8, 11, 16, 2, 10, 9]);
    heapify(&mut values, 0, 6);
    assert_eq!(values, [16, 11, 9, 2, 10, 8]);

}

#[test]
fn test_heap_sort_empty() {
    let mut values: [i32; 0] = [];
    heap_sort(&mut values);
    assert_eq!(values, [])
}

#[test]
fn test_heap_sort_one() {
    let mut values = [1];
    heap_sort(&mut values);
    assert_eq!(values, [1]);
}

#[test]
fn test_heap_multi() {
    let mut values = [9, 8, 7, 11, 10];
    heap_sort(&mut values);
    let values_expected: Vec<_> = (7..12).collect();
    assert_eq!(values_expected, values);
}

quickcheck! {
    fn test_heap_everything(xs: Vec<i32>) -> bool {
        // Macro doesn't allow `mut` in the `fn` declaration :-(
        let mut xs = xs;
        let mut expected_sorted = xs.clone();
        expected_sorted.sort();
        heap_sort(&mut xs);
        expected_sorted == xs
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.