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.
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 :
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.
