Trier un tableau sans utiliser "sort"

Ce que vous devez connaitre : - Les tableaux
- Les boucles et conditions
- les méthodes

Le but est de trier un tableau dans l'ordre croissant sans utiliser la méthode "sort"

Comment le réaliser ?

Il suffit de parcourir le tableau est de comparer l'élement n avec l'élément suivant dans le tableau. Lorsque vous avez finis de parcourir le tableau, il faut recommencer de parcourir autant de fois qu'il y a d'élement dans le tableau. C'est une méthode pour trier un tableau simple à réaliser mais loin d'être la plus performante. C'est le trie Bulle.

Voici un exemple :

Code Ruby

t = [1, 5, 4]

Nous allons comparer 1 et 5. Puisque 1 est bien plus petit que 5, on ne les change pas. On teste maintenant 5 et 4... puisque 5 et supérieur à 4, on change leurs positions. On parcourir ensuite 3 fois le tableau pour vérifier si il n'y pas d'autres éléments à changer.

A vous de jouer :)

Réponse :

Nous allons faire une méthode :

Code Ruby

def trie_bulle(tab)
       
return tab
end

Cette méthode nous retournera le tableau trié.

Maintenant, nous allons mettre deux boucles.

Code Ruby

def trie_bulle(tab)
        for i in 0..tab.size
                for j in 0..tab.size - 2
                       
                        # Condition pour tester les éléments
       
                end
        end
return tab
end

La première boucle parcours le tableau autant de fois qu'il y a d'élément. La deuxième boucle parcours le tableau. Pourquoi "tab.size - 2" ? "size" est le nombre d'éléments du tableau. Il faut s'arrêter au dernier élément donc à "tab.size - 1". Puisqu' on teste l'élément avec l'élement suivant, il faut éviter de sortir de la boucle. Voilà la raison, pourquoi on mets "tab.size - 2"

Maintenant, il faut faire la condition.

Code Ruby

def trie_bulle(tab)
        for i in 0..tab.size
                for j in 0..tab.size - 2
       
                        if tab[j] > tab[j+1]
                                x = tab[j+1]
                                tab[j+1] = tab[j]
                                tab[j] = x
                        end
       
                end
        end
return tab
end

Si l'élément du tableau est supérieur à l'élément suivant, on garde en mémoire dans une variable x, l'élément suivant. Ensuite, on change les positions : "tab[j+1]" prend la valeur de "tab[j]" et "tab[j]" prend la valeur de x soit de "tab[j+1]"

Explication :

Prenons l'exemple de :

Code Ruby

t = [1, 5, 4, 2]
 trie_bulle(t)

La deuxième boucle va faire 3 tours (0 à 4-2).
tab[0] n'est pas supérieur à tab[1]. Ensuite, il compare tab[1] et tab[2]. Puisque 5 est plus grand que 4 donc on a :

x = tab[2]
tab[2] = tab[1]
tab[1] = x

soit

x = 4
tab[2] = 5
tab[1] = 4

On aura donc :

t = [1, 4, 5, 2]

Ensuite il compare t[2] avec t[3], de la même manière, on aura :

t = [1, 4, 2, 5]

La première boucle recommence le parcours du tableau ... on recommence les comparaisons. On aura à la fin :

t = [1, 2, 4, 5]

La première boucle rerecommence encore mais puisque le tableau est complètement trié, ça ne change pas le résultat.