Exercice algorithmed e tri par insertion, fusion et rapide (quicksort)

But:
Cet exercice va vous permettre de comparer de trois algorithmes de tris: le tri par insertion, le tri par fusion et le tri rapide (quicksort).
Thème:
algorithme, héritage, complexité

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();
}
}

Le "vrai" programme principal

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.

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

Fichiers:
FusionSort.java, InsertionSort.java, QuickSort.java, Tri.java


La classe abstraite Tri:

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104		abstract class Tri {

/**
* Stocke le nombre de comparaisons d'ordre sur les éléments du tableau
*/
protected int nbrTests;

/**
* Stocke le nombre de fois que l'algorithme utilise son opération élémentaire
* ex: pour Quicksort l'opération élémentaire est la permutation (ou 'swap'
* en anglais) de deux éléments du tableau
*/
protected int nbrOps;

/**
* Ne sert qu'à l'affichage.
* Ce tableau stocke les valeurs des éléments du tableau avant qu'ils ne soient triés.
*/
protected int[] tableauEntree;

/**
* Le tableau sur lequel l'algorithme de tri travaille
*/
protected int[] tableauTrie;


/**
* Champs d'information sur le tri utilisé.
* Il peuvent être redéfinis dans les sous classes
* Ex: nomTri = "quickSort"et nomOp = "swap"; dans le constructeur
* de QuickSort
*/
protected String nomTri = "tri quelconque";
protected String nomOp = "operation quelconque";

public void initialiser(int[] unTableau) {
nbrTests = 0;
nbrOps = 0;
tableauEntree = new int[unTableau.length];
tableauTrie = new int[unTableau.length];
for (int i = 0; i tableauEntree[i] = unTableau[i];
tableauTrie[i] = unTableau[i];
}
}

/**
* La méthode de tri propre à chaque sous-classe
* sera définie dans la sous-classe.
*/
public int trier() {
nbrTests = 0;
nbrOps = 0;

algorithmeTri(0, tableauTrie.length - 1);

return (nbrTests + nbrOps);
}

/**
* algorithmeTri sera défini dans les sous classes
*/
abstract void algorithmeTri(int indiceMin, int indiceMax);

/**
* Ici au lieu de définir une méthode affiche, on redéfinit la méthode
* toString qui est appellée automatiquement quand on fait un print de
* l'objet.
* ex: System.out.println(new QuickSort(new double[] {1 2}))
* va afficher le nombre d'opérations effectuées par QuickSort
* pour trier le tableau {1, 2}
*/
public String toString() {
String marker = " *** ";
String size = "" + tableauEntree.length;
String input = "";
for (int i = 0; i input = input + tableauEntree[i] + " ";
}

// ? est un opérateur ternaire permettant de
// faire la même chose qu'un if-then-else:
// (cond) ? siOui : siNon
String stats = nbrTests + " test d'ordre " + ((nbrTests > 1) ? "s" : "") + " and " +
nbrOps + " " + nomOp + ((nbrOps > 1) ? "s" : "");

return marker + nomTri + ": " + input + "\n" + marker +
" -> " + getSortedString(0, tableauTrie.length - 1) + "\n" +
marker + "taille du tableau d'entrée: " + size + "\n" +
marker + "a requis " + stats;
}

public String getSortedString(int inf, int sup) {
String output = "";
inf = ((inf sup = ((sup >= tableauTrie.length) ? tableauTrie.length - 1 : sup);
if (inf for (int i = inf; i output = output + tableauTrie[i] + " ";
}
}
return output;
}
}

La sous classe pour le tri par insertion

InsertionSort.java
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		/**
* ***********************************************************
* Tri par insertion
* Classe fournissant l'algorithme de tri ainsi que les éléments
* d'informations permettant de le tester empiriquement
* ************************************************************
*/
class InsertionSort extends Tri {

// Constructeur de l'objet tri par insertion
public InsertionSort() {
nomTri = "Tri par insertion";
nomOp = "swap";
}

// Tri par insertion: si l'on part d'un tableau trié et qu'on lui ajoute un
// élément à la bonne place on obtient de nouveau un tableau trié
// On commence avec le premier élément comme tableau trié initial
public void algorithmeTri(int g, int d) {
int i, j;
int temp;
for (i = g + 1; i temp = tableauTrie[i];
j = i - 1;
while ((j >= 0) && (tableauTrie[j] > temp)) {
tableauTrie[j + 1] = tableauTrie[j];
nbrOp++;
nbrTest++; // On compte les comparaisons et permutations
j--;
}
tableauTrie[j + 1] = temp;
}
}

}

La sous classe pour le tri par fusion:
L'algorithme implémenté ici part de l'hypothèse restrictive que les tableaux ont pour tailles des puissances de 2 (c-àd: 2n, n quelconque), ce qui corresponds au cas de fonctionnement optimal pour l'algorithme et aux données qui vous sont fournies dans les jeux de tests. Comme exercice complémentaire vous pourrez le généraliser.

FusionSort.java
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74		/**
* ***********************************************************
* Tri par fusion
* classe fournissant l'algorithme de tri ainsi que les éléments
* d'informations permettant de le tester empiriquement
* ************************************************************
*/
class FusionSort extends Tri {

/**
* Tableau intermédiaire permettant de faire la fusion
*/
private int[] temp;

/**
* Constructeur
*/
public FusionSort() {
nomTri = "Tri par fusion";
nomOp = "assignation";
}

public int trier() {
temp = new int[tableauEntree.length];
return (super.trier());
}

/**
* Algorithme de tri par fusion
*/
void algorithmeTri(int g, int d) {
int i, j, k;
// On suppose un tableau de taille 2^n
// g = borne gauche
// d = borne droite
// m = milieu (dernier élément de la partie gauche)

// Condition d'arret de la récursion
if (g int m = (g + d - 1) / 2;
// La récursion
algorithmeTri(g, m);
algorithmeTri(m + 1, d);

// On reclasse les éléments des deux tableaux dans l'ordre suivant :
// tableau1 (du plus petit au plus grand) tableau2 (du plus grand au plus petit),
// afin d'éviter de sortir des limites du tableau lors des assignations
for (k = g; k temp[k] = tableauTrie[k];
}
for (k = m + 1; k temp[d + m + 1 - k] = tableauTrie[k];
}

i = g;
j = d;

// Fusion de deux tableaux trié en un
for (k = g; k if (temp[i] tableauTrie[k] = temp[i];
i++;
nbrTest++;
nbrOp++; // On compte le nb d'assignations et de comparaisons
} else {
tableauTrie[k] = temp[j];
j--;
nbrTest++;
nbrOp++; // On compte le nb d'assignations et de comparaisons
}
}
}
}
}

La sous classe pour le tri rapide:

QuickSort.java
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65		/**
* ***********************************************************
* Tri rapide
* Classe fournissant l'algorithme de tri ainsi que les éléments
* d'informations permettant de le tester empiriquement
* ************************************************************
*/
class QuickSort extends Tri {
public QuickSort() {
nomTri = "quickSort";
nomOp = "swap";
}

public void algorithmeTri(int inf, int sup) {
if (inf
int i = inf + 1;
int j = sup;

// Séparation du tableau en deux sous-tableaux:
// - l'un dont les éléments sont plus petits que l'élément pivot [inf]
// - l'autre dont les éléments sont plus grands ou égaux à [inf]
// L'indice de séparation est j:
// [j] est plus grand que tout les éléments [i] tels que i // [j] est plus petit que tous les éléments [i] tels que i>j
//

while (j > i) {
// La boucle s'arrête quand j == i-1
// ou j==i(quand [inf] est le plus grand élément du tableau)

while (i nbrTest++;
i++;
}
while (j > inf && tableauTrie[j] >= tableauTrie[inf]) {
nbrTest++;
j--;
}
if (i swap(i, j);
}
}

if (tableauTrie[inf] > tableauTrie[j]) {
nbrTest++;
swap(inf, j);
}
if (j - 1 > inf) {
algorithmeTri(inf, j - 1);
}
if (j + 1 algorithmeTri(j + 1, sup);
}
}
}

private void swap(int i, int j) {
nbrOp++;
int temp = tableauTrie[i];
tableauTrie[i] = tableauTrie[j];
tableauTrie[j] = temp;

}
}
Article publié le 15 Août 2010 Mise à jour le Lundi, 31 Août 2020 18:55 par Salim KHALIL