Algorithmics with Rust: Bubble sort

Originally post on my blog.

Hello, today we are going to talk about the bubble sort.

"Bubble sort?"

The bubble sort is a simple algorithm which will help us to get along with Rust syntax and to understand what is the algorithm complexity which we talk about in the previous post.

"Ok, what does it do?"

In short, this algorithm compare all elements in an array two by two and it swap there positions if the two element are not sorted.

It takes an array in and gives an array out.

fn bubble_sort(vec_to_sort: &Vec<i32>) -> Vec<i32> {
    let mut result = vec_to_sort.clone();
    return result;
}

We define here function (fn) "bubble_sort". It takes "vec_to_sort" which is a vector (kind of dynamic array) of i32 or integer write on 32 bits an give us out another vector of i32.

Then we iterate and compare two by two all elements.

fn bubble_sort(vec_to_sort: &Vec<i32>) -> Vec<i32> {
    let mut result = vec_to_sort.clone();
    for i in 0..result.len() {
        for y in 0..result.len() {
            if result[i] < result[y] {
            }
        }
    }
    return result;
}

And finally, we swap the position of elements if needed.

fn bubble_sort(vec_to_sort: &Vec<i32>) -> Vec<i32> {
    let mut result = vec_to_sort.clone();
    for i in 0..result.len() {
        for y in 0..result.len() {
            if result[i] < result[y] {
                result.swap(i, y);
            }
        }
    }
    return result;
}

You can test this code here.

Count the actions, shall we?

1. We copy the input array, not relevant
2. We iterate other the n elements of the array: n actions.
3. We iterate other the n elements of the array: n actions.
4. We compare the both elements.
5. We swap, if needed, the elements.

In the worst case, we got n*n*1+1 actions. Constants are not relevant so we got a complexity of O(n²).

To get a better idea of what it means, if we got a processor able to execute 100 operations by seconds and an input array of 100 elements, this algorithm will take 1m40 to sort this array.

"Ok, fine for the algorithm... What about my array is made of strings? Or if I want to sort it differently?"

Nice one! To do so, we have to make the function generic and use closures (sort of unnamed function).

We can then modify the code like that:

fn bubble_sort<T: std::clone::Clone, F>(vec_to_sort: &Vec<T>, compar : F) -> Vec<T> 
where F : Fn(&T,&T) -> bool {
    let mut result = vec_to_sort.clone();
    for i in 0..result.len() {
        for y in 0..result.len() {
            if compar(&result[i], &result[y]) {
                result.swap(i, y);
            }
        }
    }
    return result;
}

We say here that the function is parameterized against T and F where F is a function which will return a boolean.

To see how it works, look here.

It is done for this one, see you soon for another one.

-- Mathieu