@Mathieu Nivoliez

Algorithmique avec Rust: Tri à bulle

2017-04-26 / 2 minutes.

Bonjour, aujourd'hui on va parler du tri à bulle.

"Le tri à bulle?"

Le tri à bulle est un algorithme simple qui nous permettra de nous familiariser avec l'algorithmie en Rust et également qui nous permettra de comprendre ce que signifie la complexité algorithmique dont nous avons parlé dans le précédent article.

"Ok, en quoi il consiste ce tri à bulle?"

Basiquement, cette algorithme compare deux à deux tous les éléments d'un tableau et les permute s'il sont mal trié.

Donc nous avons un algorithme qui prend un tableau en entrée et donne un tableau en sortie.

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

Nous définissons ici une fonction, avec le mot clé "fn", qui se nomme "bubble_sort". Elle prend en paramètre une variable appelée "vec_to_sort" qui est un vecteur de i32. Un vecteur est un tableau qui change de taille au court du temps et un i32 est un entier écrit sur 32 bit. Cette fonction retourne un autre vecteur de i32.

L'algorithme compare tous les éléments deux à deux.

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;
}

Puis, nous permutons les éléments s'ils sont mal triés.

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;
}

Vous pouvez tester ce code ici.

Comptons maintenant les actions.

  1. La copie du tableau d'entrée est négligeable.
  2. Nous bouclons ensuite sur tous les éléments: n actions.
  3. Nous rebouclons ensuite sur tous les éléments: n actions.
  4. On compare les éléments entre eux.
  5. On échange, si besoins, les éléments.

On a donc dans le pire des cas n*n*1+1 actions. Or les constantes ne sont pas importantes donc nous avons une complexité en O(n2).

Pour donner une idée de ce que cela représente, si nous avons un processeur capable d'exécuter 100 opérations par secondes et que nous avons un tableau de 100 éléments, cette algorithme mettra 1m40 à trier ce tableau.

"Bon, ok pour l'algo... Et si on veux trier un tableau avec des chaînes de caractères? Ou même le trier du plus grand au plus petit?"

Bonne remarque! Pour cela, il faut que la fonction devienne générique et qu'elle fasse appelle aux closures (des sortes de fonction anonyme).

Nous pouvons ainsi modifier le code comme cela:

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;
}

Basiquement, nous indiquons que la fonction se paramètre avec T et F où F sera une fonction retournant un booléen.

Pour voir comment fonctionne ce code c'est ici.

Voila c'est finit pour cet algorithme, on se revoit la prochaine fois pour un autre algorithme.

-- Mathieu