Exercice java corrigé algorithme de tri par insertion, fusion et rapide (quicksort)

Exercice java corrigé algorithme de tri par insertion, fusion et rapide (quicksort), tutoriel java et document pdf.

Cet exercice va vous permettre de comparer trois algorithmes de tris: le tri par insertion, le tri par fusion et le tri rapide (quicksort). Cette comparaison sera empirique (c’est-à-dire basée sur l’expérimentation) et jaugera les performances en moyenne des algorithmes. Il s’agit ici de trier des séquences de nombres entiers, stockés dans des tableaux.

On considérera qu’un algorithme de tri est caractérisé par un nombre d’opérations élémentaires (nbrOps) nécessaires, et par le nombre de comparaisons d’ordre (nbrTests) entre les éléments du tableau. Une opération élémentaire peut être une affectation ou une permutation par exemple. C’est la somme de ces deux mesures qui va déterminer la complexité de l’algorithme.

Une classe abstraite pour les algorithmes de tri

Dans cet exercice on représentera un algorithme de tri par une classe abstraite Tri dotée des attributs suivants:

1. une chaine de caractères, nomTri, donnant le nom de l’algorithme de tri
2. un tableau d’entiers à trier tableauEntree
3. un tableau d’entiers trié tableauTrie
4. une chaine de caractères nomOp donnant le nom de l’opération élémentaire considérée pour l’évaluation de la complexité de l’algorithme (par exemple "permutation").
5. un entier nbrOps donnant le nombre de fois que l’opération élémentaire est exécutée par l’algorithme pour obtenir tableauTrie à partir de tableauEntree.
6. un entier nbrTests donnant le nombre de comparaisons d’ordre exécutées par l’algorithme pour obtenir tableauTrie à partir de tableauEntree.

Par ailleurs, votre classe Tri comportera les méthodes suivantes:

1. une constructeur initialisant nomOp à "opération quelconque", nomTri à "algorithme de tri quelconque", et nbrOps et nbrTests à zéro.
2. une méthode initialiser prenant en paramètre un tableau d’entiers et initialisant tableauEntree au moyen de son contenu. Cette méthode devra également remettre à zéro nbrOps et nbrTests
3. une méthode abstraite algorithmeTri prenant en paramètre deux entiers correspondant aux indices entres lesquels il faut trier le tableau.
4. une méthode trier:
   1. invoquant algorithmeTri sur le tableau d’entrée entier (c’est à dire entre 0 et tableauEntier.length-1)
   2. et retournant un entier correspondant à la somme de nbrOps et nbrTests
5. une méthode affiche permettant d’afficher un objet de type Tri d’une façon qui vous semble suffisamment informative, par exemple:

   QuickSort: 
   Séquence d'entrée: 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23
   22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
   Séquence triée: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
   25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 
   *** taille du tableau d'entrée: 40 
   *** a requis 780 tests d'ordre et 20 permutations

Les sous-classes qui font le travail

Tri par insertion

Codez la classe InsertionSort héritant de la classe Tri. Il faudra spécifier, dans le constructeur, des valeurs appropriées pour les variables d’instance décrivant: le nom de l’algorithme (tri par insertion) et le nom de l’opération élémentaire caractérisant la complexité de l’algorithme (ici la permutation de deux éléments). Vous coderez ensuite la méthode algorithmeTri donnant corps à la méthode abstraite correspondante de la classe Tri. L’algorithme de tri par insertion à coder a été vu en cours. Il faudra incrémenter les variables nbrOps et nbrTests au bon endroit afin d’évaluer correctement la complexité empirique de l’algorithme.

Tri par fusion

Procédez de même pour l’algorithme de tri par fusion (classe FusionSort héritant de Tri). Ici les opérations élémentaires caractérisant la complexité seront le nombre de comparaisons et le nombre d’affectations de la partie fusion de l’algorithme (voir transparents du cours).

Tri rapide

.. et de trois pour l’algorithme de tri rapide (classe QuickSort héritant de Tri). Ici les opérations élémentaires caractérisant la complexité seront le nombre de comparaisons et le nombre de permutations (voir description de l’algorithme dans les transparents du cours).

Vous pourrez tester chacun de vos algorithmes au moyen d’un petit programme du style:

class TesterTri {
    public static void main(String [] args) {
        Tri sort = new FusionSort(...); // selon votre codage du constructeur
        int [] tab ={1,3,7,2,0,5};
        sort.initialiser(tab);
        sort.trier();
        sort.affiche();
    }
}

En fait, le programme principal vous est fourni dans cet exercice. Ce programme va vous permettre de comparer les trois algorithmes de tri codé précédemment. Le « vrai » programme principal

Pour que les comparaisons empiriques soient informatives, il faut:

1. que chaque test soit fait sur une taille de problème suffisamment importante
2. que des tests soient faits sur différentes tailles de problèmes: on veut voir comment la difficulté (ici nbrOps+nbrTests) évolue en fonction la taille du tableau à trier
3. que pour une taille donnée de problème on fasse plusieurs tests (on garde alors la moyenne de ces tests)

Le code qui vous est fourni vous donne les moyens de réunir ces conditions:

1. La première condition est réalisée par le fait que les données à tester ne sont pas codées en dur dans des tableaux mais mises dans des fichiers (exemple: le fichier 128_1.dat est un fichier contenant 128 entiers). Ceci permet de considérer un grand nombre de valeurs. Le programme ComparerTri va lire les données depuis le fichier et les récupérer dans des tableaux utilisables par vos classes.
2. La seconde condition est réalisée par le fait que trois tailles sont considérées pour les comparaisons: 128, 512 et 4096
3. La dernière condition est réalisée par le fait que pour une taille donnée (par exemple 128) il existe 5 fichiers de données possibles (128_1.dat … 128_5.dat). ComparerTris va faire le test sur chacun de ces fichier et calculer la moyenne des performances (moyenne des nbrOps+nbrTests pour chaque problème) sur ces 5 problèmes.

Note: Les entrées-sorties sur fichiers sont mises en oeuvre par deux classes fournies: Entree.java et Sortie.java. Les éléments de programmation nécessaires seront vus au semestre d’été. Le programme ComparerTris va en fait construire un fichier résultats par algorithme: FusionSort.dat, InsertionSort.dat et QuickSort.dat. Voici un exemple du contenu du fichier FusionSort.dat généré par les tests sur l’algorithme de tri par fusion:

128 1792.0
512 9216.0
4096 98304.0

ceci signifie que la moyenne des nbrOps+nbrTests pour les 5 fichiers de données de taille 128 est 1792.0 etc…

Visualiser les résultats

Pour avoir une meilleure idée de ce que ces résultats représentent vous utiliserez le programme gnuplot. Pour ce faire, il suffira de lancer la commande gnuplot dans un xterm et taper la commande load "sortplot.plot".
Le fichier sortplot.plot vous est fourni. Il contient des directives permettant d’afficher sous forme de courbes les données de vos fichiers résultats FusionSort.dat, Insertion.dat, QuickSort.dat).

La correction exercices java corrigés algorithme de tri par insertion, fusion et rapide (quicksort) (voir page 2 en bas)