DM – Devoir maison
On vous rappelle que le devoir est à rendre pour le vendredi 21 octobre 2022 à 23:55 au plus tard.
Bon travail !
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.
Tri par insertion (∼90mn – moyen)
Dans cet exercice, nous nous intéressons au tri par insertion. Le principe de cet algorithme est de maintenir un ensemble trié lors de l'insertion d'un nouvel élément. Vous pouvez observer une mise en œuvre intéressante de cet algorithme ici. L'algorithme de tri par insertion est particulièrement efficace pour de petits ensembles à trier, mais totalement inefficace dès que le nombre d'éléments devient grand.
Pour ajouter les valeurs au tableau sorted tout en maintenant le tableau trié, vous devez itérer sur les arguments. Pour chaque argument, vous devez procéder en trois étapes.
- Étape 1: à l'aide d'une boucle, trouvez l'emplacement dest auquel il faut insérer l'argument courant dans le tableau sorted. Pour cela, il suffit de trouver le premier élément qui est plus grand que l'argument à insérer. Notez que vous ne devez comparer que les éléments déjà insérés (c'est-à-dire que vous devez compter le nombre d'éléments insérés dans votre tableau, ça vous évitera de parcourir tout le tableau à chaque fois).
- Étape 2: ensuite, décalez d'un cran à droite la partie se trouvant à droite de dest dans le tableau sorted de façon à libérer un espace pour le nouvel entier. Pensez à copier de la droite vers la gauche pour éviter d'écraser vos valeurs.
- Étape 3: enfin, insérez le nouvel élément à l'emplacement dest.
Le petit schéma suivant illustre le principe (un point d'interrogation indique qu'aucun élément n'est encore inséré à cet emplacement dans le tableau) :
Mettez en œuvre cet algorithme.
