Implementing all the Algorithms - Day 1: Quicksort

It's day the first real day of implementing all the algorithms. I managed to implement quicksort, though to be fair, it took a bit longer overall. On Sunday, I implemented bubble sort and wrote the article in maybe 1.5 hours. Today it took me 2 hours just to get quicksort working and then another half an hour to add some nifty test suite.

Quicksort

pub fn quicksort<T: PartialOrd + Clone>(elements: &mut [T]) {
    if elements.len() < 2 {
        return;
    }
    let (left_p, right_p) = partition(elements);
    quicksort(&mut elements[0..left_p]);
    quicksort(&mut elements[right_p..]);
}


/// Partitions elements into left_side, pivots, right_side
/// returns the index of the leftmost item still being a pivot and the index of the item right of the last pivot
fn partition<T: PartialOrd + Clone>(elements: &mut [T]) -> (usize, usize) {
    let pivot = elements[elements.len() / 2].clone();
    let mut left_index = usize::MAX;
    let mut right_index = elements.len();

    loop {
        loop {
            left_index = left_index.wrapping_add(1);
            if elements[left_index] >= pivot {
                break;
            }
        }

        loop {
            right_index -= 1;
            if elements[right_index] <= pivot {
                break;
            }
        }

        if left_index >= right_index {
            break;
        }

        unsafe { swap_elements_unsafe(elements, left_index, right_index) }
    }

    // find the two indexes of elements where the pivots begin and end 
    // when there are multiple copies of the pivot

    while left_index > 0  {
        left_index -=1;
        if elements[left_index] != pivot {
            left_index += 1;
            break;
        }
    }

    while right_index < elements.len() -1 && elements[right_index] == pivot {
        right_index += 1;
    }

    (left_index, right_index)
}

This one is considerably longer than the simple bubble sort. I mostly kept to the easiest implementation with two design decisions to avoid certain worst-case edge cases. First I chose the pivot to be the element in the middle of the slice to avoid worst-case runtime behavior when the array is already sorted. Second I chose to apply the slight variation of returning two indexes instead of just one. The first points to the leftmost element that is still a pivot and the second points to the element after the pivot. That avoids having worst-case behavior when sorting a slice of elements having all equal elements.

Testing

On top of implementing quicksort, I also wanted to juice up the test suite a bit. To do so, I wanted to abstract away tests that are always the same. At first, I just created a function that performs all three tests and assertions.

This didn't make me happy though, because it felt like I had no overview of which tests were failing. After checking if there was some API to report test case success directly and digging through the code, I found out that apparently the #[test] macro is built into the compiler:

#[stable(feature = "rust1", since = "1.0.0")]
#[allow_internal_unstable(test, rustc_attrs)]
#[rustc_builtin_macro]
pub macro test($item:item) {
    /* compiler built-in */
}

My second approach showed to be more useful. I simply created a procedural macro containing the three basic tests I always want to run:

macro_rules! basic_sorting_tests {
    ($fnname: ident) => {
        #[test]
        fn it_sorts_empty_slices() {
            let mut data: [i32; 0] = [];
            $fnname(&mut data);
        }

        #[test]
        fn it_sorts_one_element_slices() {
            let mut data = [1];
            $fnname(&mut data);
        }

        #[test]
        fn it_sorts_element_slices_of_same_elements() {
            let mut data = [1, 1, 1, 1, 1, 1, 1];
            $fnname(&mut data);
        }
    };
}

This turned out to work even better than I expected. Once again the rust tooling blew me away by allowing me to run the tests individually directly from my IDE, even though they were behind a macro.

.

The only downside it has for me is that it doesn't get me into a test-driven development flow but to be honest I rarely do that stringently anyways.

In any case, I enjoyed this one, especially because it is a bit more practical than bubble sort.