Portail informatique Année 2018 – 2019

CSC 3101 – Algorithmique et langage de programmation

On vous rappelle que le devoir est à rendre pour le vendredi 30 novembre 2018 à 23:55 au plus tard.

Pour la remise, il faut déposer les fichiers sources (extension .java) sous moodle.
Ce devoir maison a pour objectif de conforter vos connaissances en Java et de vous présenter des algorithmes de tri. Trier des nombres est l'une des activités favorites des informaticiens car de nombreux programmes ont besoin de présenter des éléments de façon ordonnée (photos, films, noms, ...). De plus, comme vous l'avez probablement vous-même constaté, il est beaucoup plus rapide de rechercher un élément dans un ensemble trié que dans un ensemble non trié (pensez au temps qu'il vous faudrait pour chercher un mot dans un dictionnaire dans lequel les mots seraient ordonnés de façon aléatoire).

La charge de travail personnel prévisionnelle pour ce DM est estimée à 2h30. Le devoir doit être rendu via la section dédiée sur la page Moodle du cours. Vous êtes incité(e)s à réaliser ce devoir seul afin de vous familiariser avec le langage Java. Vous êtes néanmoins autorisés à le réaliser en binôme. (dans ce cas, l'un doit rendre le devoir tandis que l'autre doit rendre sous Moodle un fichier indiquant uniquement le nom du binôme avec qui il a travaillé – pensez aussi à indiquer dans vos fichiers sources les noms des membres du binôme).

Bon travail ! 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 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.

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 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. Créez un projet nommé isort et une classe InsertionSort contenant une méthode main. Affichez les paramètres de votre programme après avoir spécifié que les paramètres sont 8 6 1 3 5 2. Créez un tableau nommé sorted ayant autant de cases que le tableau des arguments du programme. Complétez votre programme de façon à afficher les éléments du tableau sorted. Votre programme devrait afficher 6 fois l'entier 0 puisque vous avez 6 arguments et puisque un tableau est toujours pré-initialisé avec des 0 en Java. 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 à commencer à copier les éléments en partant de la droite du tableau pour éviter d'écraser les 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) : Insertion de l'élément 8: État initial: Nombre d'éléments déjà insérés: 0 Tableau: [? ? ? ? ? ?] Étape 1: Trouver la position à laquelle insérer l'élément Emplacement d'insertion: 0 (car 8 est plus grand que tous les éléments déjà insérés) Étape 2: Décaler d'un cran à droite la partie droite du tableau Nombre d'éléments déjà insérés: 0 Tableau: [? ? ? ? ? ?] Étape 3: Insérer l'élément 8 Nombre d'éléments déjà insérés: 1 Tableau: [8 ? ? ? ? ?] ... Insertion de l'élément 3: État initial: Nombre d'éléments déjà insérés: 3 Tableau: [1 6 8 ? ? ?] Étape 1: Trouver la position à laquelle insérer l'élément Emplacement d'insertion: 2 (car l'élément 6 est plus grand que l'élément 3 à insérer) Étape 2: Décaler d'un cran à droite la partie droite du tableau Nombre d'éléments déjà insérés: 3 Tableau: [1 6 6 8 ? ?] Étape 3: Insérer l'élément 3 Nombre d'éléments déjà insérés: 4 Tableau: [1 3 6 8 ? ?]

Mettez en œuvre cet algorithme.