CSC 3101 – Algorithmique et langage de programmation

Portail informatique

Tri à bulles (∼60mn – moyen)

Dans cet exercice, nous étudions un algorithme de tri classique : le tri à bulles. Cet algorithme est toujours inefficace, mais il est intéressant à mettre en œuvre car il est simple. Le tri à bulles est un algorithme de tri en place, c'est-à-dire que l'algorithme trie un tableau désordonné. Le principe de l'algorithme est de faire monter les valeurs les plus hautes en haut du tableau, un peu comme des bulles.

Créez un projet nommé bsort et une classe BubbleSort contenant une méthode main. Dans votre méthode main, définissez une variable tab référençant un tableau de doubles et affectez-lui un tableau contenant les valeurs 2.3, 17.0, 3.14, 8.83, 7.26. Affichez chaque élément du tableau.

Il est important que le tableau soit un tableau de double et non de float. En effet, par défaut, Java considère qu'un nombre à virgule flottante est un double et non un float. Le tableau { 2.3, 17.0, 3.14, 8.83, 7.26 } créé par Java est donc un tableau de double, qui ne peut alors pas être affecté à un tableau de float.

Pour faire monter les bulles dans le tableau, nous le parcourons de droite (fin du tableau) à gauche (début du tableau) avec une variable d'indice i. Ensuite, pour chaque i, il faut faire remonter la plus grande valeur jusqu'à l'emplacement i avant de passer à l'itération suivante (i-1). La figure suivante illustre le principe :

État initial 2.3 17.0 3.14 8.83 7.26 i = 4 ^ i Remonte la plus grande bulle avec j va de 0 à i - 1 => 2.3 3.14 8.83 7.26 17.0 i = 4 ^ i c Recommence avec i = 3

Initialement, i vaut 4 (taille du tableau - 1). On parcourt le tableau avec variable j allant de 0 à i - 1 pour faire remonter la plus grande bulle. A chaque fois que tab[j] est plus grand que tab[j+1], il faut donc inverser les deux cases. L'état après ce parcours est donné à la fin de la figure. Ensuite, il suffit de recommencer avec i égal 3 puisque l'élément en tab[4] est bien placé. Vous pouvez observer une mise en œuvre intéressante de cet algorithme ici.