Portail informatique Année 2018 – 2019

CSC 3101 – Algorithmique et langage de programmation

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.