CSC 3101 – Algorithmique et langage de programmation

DM – Devoir maison

On vous rappelle que le devoir est à rendre pour le vendredi 27 octobre 2024 à 23:55 au plus tard.

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 !

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

Tri par insertion (∼30mn – 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.

Dans le projet tri, créez une classe InsertionSort contenant une méthode main.

Affichez les arguments de votre programme après avoir spécifié que les arguments sont 4 6 -1 3 5 2.

Créez un tableau tab contenant les arguments du programme, mais représentés par des double.

double[] tab = new double[args.length]; for (int i = 0; i

Créez une méthode classe sort prenant en entrée un tableau de double et retournant un tableau de double. Dans cette méthode, créez un tableau nommé sorted ayant autant de cases que le tableau des arguments du programme. La méthode doit retourner ce tableau.

Complétez votre programme de façon à afficher les éléments du tableau sorted dans la fonction main. Pour cela, appelez la fonction sort sur tab et récupérez la sortie (non triée pour l'instant). Votre programme devrait afficher 6 fois l'entier 0 puisque vous avez 6 arguments et parce qu'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 à 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) :

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 ? ?]

Commencez par écrire une fonction findInsertion qui prend en entrée un tableau de double (ce sera sorted), l'élément à insérer, et l'indice de fin du tableau et qui retourne un entier représentant la position où insérer notre élément.

static int findInsertion(double[] sorted, double value, int insertedCount) { // On cherche le premier élément strictement plus grand que 'value' for (int i = 0; i value) { return i; } } // Si aucun élément n'est plus grand, on insère en fin de la partie utilisée return insertedCount; }

Écrivez un fonction shift prenant en entrée un tableau de double et un indice. Cette fonction décale en place tous les éléments du tableau d'un cran vers la droite à partir de l'indice donné (et ne retourne rien).

static void shift(double[] sorted, int fromIndex, int insertedCount) { for (int i = insertedCount; i > fromIndex; i--) { sorted[i] = sorted[i - 1]; } // La case 'fromIndex' sera écrasée par l'insertion qui suit }

Finalement, implémentez la fonction sort.

static double[] sort(double[] input) { double[] sorted = new double[input.length]; // pré-initialisé à 0.0 int insertedCount = 0; for (int i = 0; i

Quelle est la complexité du tri par insertion dans le pire des cas ?

Dans le pire des cas, le tableau est trié dans l’ordre décroissant. Chaque nouvel élément doit être inséré tout au début. Donc pour le i-ème élément, il faut décaler i cases. Nombre total de décalages/comparaisons ≈ 1 + 2 + … + (n-1) = n(n-1)/2. On a une complexité de O(n²).