CSC 3101 – Algorithmique et langage de programmation

Tri à bulles (∼20mn – 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é tri 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). Dans cet exercice, n'utilisez pas 4 : les méthodes doivent fonctionner avec n'importe quelle entrée. On parcourt le tableau avec variable j allant de 0 à i - 1 pour faire remonter la plus grande bulle. À 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.

Commencez par écrire une méthode de classe swap prenant en entrée un tableau de double, un indice i et un indice j et modifiant le tableau pour inverser les valeurs stockées en i et j. Cette fonction ne retourne rien (réfléchissez pourquoi).

static void swap(double[] tab, int i, int j) { double temp = tab[i]; tab[i] = tab[j]; tab[j] = temp; }

Écrivez une méthode de classe sort prenant en entrée un tableau de double et qui le trie en place. La méthode ne retourne rien.

static void sort(double[] tab) { int n = tab.length; // On fait remonter les bulles de droite à gauche for (int i = n - 1; i > 0; i--) { for (int j = 0; j tab[j + 1]) { swap(tab, j, j + 1); } } } }

Dans main, triez votre tableau et affichez-le.

// Méthode utilitaire pour afficher un tableau static void printArray(double[] tab) { for (double val : tab) { System.out.print(val + " "); } System.out.println(); } // Méthode main public static void main(String[] args) { double[] tab = { 2.3, 17.0, 3.14, 8.83, 7.26 }; System.out.println("Tableau initial :"); printArray(tab); // Tri du tableau sort(tab); System.out.println("Tableau trié :"); printArray(tab); }

Quelle est la complexité de cet algorithme dans le pire des cas ?

La complexité est quadratique en la taille du tableau dans le pire des cas (deux boucles imbriquées = n + (n-1) + (n-2) + ... + 1).