Algorithmics with Rust: Bubble sort
Tags: rustmathematics
Published: 2017-04-26 10:43:26

---
title: "Algorithmics with Rust: Bubble sort"
published: true
description: 
tags: Rust Mathematics
---
*Originally post on my [blog](https://mathieu-nivoliez.com/posts/2017-04-26-algorithmics-with-rust-bubble-sort/).*

<p style="text-align: justify;">Hello, today we are going to talk about the bubble sort.</p>

<h2 style="text-align: justify;">"Bubble sort?"</h2>
<p style="text-align: justify;">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.</p>

<h2 style="text-align: justify;">"Ok, what does it do?"</h2>
<p style="text-align: justify;">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.</p>
<p style="text-align: justify;">It takes an array in and gives an array out.</p>

```rust
fn bubble_sort(vec_to_sort: &Vec<i32>) -> Vec<i32> {
    let mut result = vec_to_sort.clone();
    return result;
}
```
<p style="text-align: justify;">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.</p>
<p style="text-align: justify;">Then we iterate and compare two by two all elements.</p>

```rust
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;
}
```
<p style="text-align: justify;">And finally, we swap the position of elements if needed.</p>

```rust
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;
}
```
<p style="text-align: justify;">You can test this code <a href="https://is.gd/OLZuLj">here</a>.</p>
<p style="text-align: justify;">Count the actions, shall we?</p>

<ol style="text-align: justify;">
 	<li>We copy the input array, not relevant</li>
 	<li>We iterate other the n elements of the array: n actions.</li>
 	<li>We iterate other the n elements of the array: n actions.</li>
 	<li>We compare the both elements.</li>
 	<li>We swap, if needed, the elements.</li>
</ol>
<p style="text-align: justify;">In the worst case, we got n*n*1+1 actions. Constants are not relevant so we got a complexity of O(n<sup>2</sup>).</p>
<p style="text-align: justify;">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.</p>

<h2 style="text-align: justify;">"Ok, fine for the algorithm... What about my array is made of strings? Or if I want to sort it differently?"</h2>
<p style="text-align: justify;">Nice one! To do so, we have to make the function generic and use <a href="https://doc.rust-lang.org/book/closures.html">closures</a> (sort of unnamed function).</p>
<p style="text-align: justify;">We can then modify the code like that:</p>

```rust
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;
}
```
<p style="text-align: justify;">We say here that the function is parameterized against T and F where F is a function which will return a boolean.</p>
<p style="text-align: justify;">To see how it works, look <a href="https://is.gd/sXT7Wd">here</a>.</p>
<p style="text-align: justify;">It is done for this one, see you soon for another one.</p>
<p style="text-align: right;">-- Mathieu</p>