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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
| import java.util.Random; // Import l'outil Random
import java.util.Scanner; // Import l'outil Scanner
public class TableauElement { // on a une classe TableauElement, pour tester les différents types de tris
private int taille; // taille du tableau
private Element [] elements; // tableau d'objets Element
final int VALEUR_MAXIMUM = 15000; // on peut changer la valeur fixé par "15000" pour les grandes valeurs
private static int operationElementaireBulle = 0; // compteur d'opération élémentaire du tri à bulle
private static int operationElementaireRapide = 0; // compteur d'opération élémentaire du tri rapide
private static int operationElementaireDenombrement = 0; // compteur d'opération élémentaire du tri à dénombrement
public TableauElement () { // constructeur sans paramètres pour créer des éléments en récupérant les entrées du clavier
Scanner scanner = new Scanner (System.in); // affiche ce que l'on tape au clavier
System.out.println ("Saisissez la \"taille\" que les tableaux manuelles vont prendre : "); // affiche manuellement la taille des tableaux
this.taille = scanner.nextInt (); // prendre l'entrée de la taillle du tableau
if (this.taille == 0) { // initialise la taille du tableau à 0
this.elements = new Element [0];
}
this.elements = new Element [this.taille];
int cle;
for (int i = 0; i < this.taille; i++) { // initialisation de la taille du tableau à 0
System.out.println ("Entrez la cle entre 0 et " + VALEUR_MAXIMUM); // affiche la valeur maximum de la clé
cle = scanner.nextInt (); // prendre l'entrée de la cle
while (cle <= 0 || cle > VALEUR_MAXIMUM) { // la clé est comprise entre 0 et la valeur maximal
System.out.println ("Nombre incorrect. Entrez la cle entre et " + VALEUR_MAXIMUM); // affiche une erreur et on redonne une valeur maximum pour la clé
cle = scanner.nextInt (); // prendre l'entrée de la cle
}
elements [i] = new Element (cle, genereValeur ());
}
scanner.close ();
}
public TableauElement (int taille) { // constructeur pour créer un tableauElément avec le paramètre taille (taille du tableau éléments de l'objet)
this.taille = taille;
this.elements = new Element [taille];
}
public TableauElement (TableauElement tableauElement){ // constructeur par recopie de paramètre tableauElement, qui est l'objet à recopier
this.taille = tableauElement.taille;
this.elements = new Element [this.taille];
if (tableauElement.taille >= 0) { // taille du tableau d'élément supérieur à 0
System.arraycopy (tableauElement.elements, 0, this.elements, 0, tableauElement.taille); // affiche la copie des éléments de tableauElement dans le TableauElement de l'objet courant
}
}
public int getTaille () { // retourne la taille du TableauElement de l'objet courant et revoit un int
return this.taille;
}
public int genereCle (int grandeur) { // génère une clé aléatoire et renvoit un int
Random random = new Random ();
return random.nextInt (grandeur);
}
public String genereValeur () { // génère une valeur aléatoire et renvoit un String
Random random = new Random ();
char caractere = (char) (random.nextInt (26) + 65);
return "" + caractere;
}
public static int demanderBorne () { // demande la grandeur que la clé générée aléatoirement va prendre et renvoit un int
Scanner scanner = new Scanner (System.in); // affiche ce que l'on tape au clavier
System.out.println ("Saisissez la \"grandeur\" des valeurs que les cles d'un Element va prendre : "); // affiche la grandeur pour des valeurs de clés d'éléments
int grandeur = scanner.nextInt (); // prendre l'entrée de la grandeur (nombre)
scanner.close ();
return grandeur;
}
public static int demanderTaille () { // demande la taille que les tableaux remplis aléatoirement vont prendre et renvoit un int
Scanner scanner = new Scanner (System.in); // affiche ce que l'on tape au clavier
System.out.println ("Saisissez la \"taille\" que les tableaux aleatoires vont prendre : "); // affiche aléatoirement la taille des tableaux
int tailleTableau = scanner.nextInt (); // prendre l'entrée de tailleTableau (nombre)
scanner.close ();
return tailleTableau;
}
public void afficherDuree (String triNom,double debut, double fin) { // calcul la durée d'exécution avec paramètre triNom, qui est le nom du tri puis avec des paramètres debut, qui est le début du temps et fin, qui est la fin du temps
double duree = fin - debut;
System.out.println (triNom + " => temps ecoule en secondes = " + (duree / 1000000)); // afffiche le nom du tri avec le temps que l'on divise par 1000000 pour mettre en millisecondes
}
public void afficherTriBulle () { // affiche les éléments du tableau avant le tri à bulle et après le tri à bulle avec la durée d'exécution
if (this.taille > 0) { // taille du tableau supérieur à 0
System.out.println ("tableau Bulle avant triBulle : \n" + this); // affiche les éléments du tableau avant le tri à bulle
double debutTempsBulle = System.nanoTime ();
this.triBulle ();
double finTempsBulle = System.nanoTime ();
System.out.println ("tableau Bulle apres triBulle : \n" + this); // affiche les éléments du tableau après le tri à bulle
afficherDuree ("Tri Bulle", debutTempsBulle, finTempsBulle);
System.out.println ("nombre d'operations elementaires tri bulle : " + operationElementaireBulle); // affiche la durée d'exécution du tri à bulle
} else { // retourne une erreur
System.out.println ("tableau Bulle de taille <= 0"); // affiche une erreur
}
}
public void afficherTriRapide () { // affiche les éléments du tableau avant le tri rapide et après le tri rapide avec la durée d'exécution
if (this.taille > 0) { // taille du tableau supérieur à 0
System.out.println ("tableau Rapide avant triRapide : \n" + this); // affiche les éléments du tableau avant le tri rapide
double debutTempsRapide = System.nanoTime ();
this.triRapide (0, this.getTaille () - 1);
double finTempsRapide = System.nanoTime ();
System.out.println ("tableau Rapide apres triRapide : \n" + this); // affiche les éléments du tableau après le tri rapide
afficherDuree ("Tri Rapide", debutTempsRapide, finTempsRapide);
System.out.println ("nombre d'operations elementaires tri rapide : " + operationElementaireRapide); // affiche la durée d'exécution du tri rapide
} else { // retourne une erreur
System.out.println ("tableau Rapide de taille <= 0"); // affiche une erreur
}
}
public void afficherTriDenombrement () { // affiche les éléments du tableau avant le tri par dénombrement et après le tri par dénombrement avec la durée d'exécution
if (this.taille > 0) { // taille du tableau supérieur à 0
System.out.println ("tableau Denombrement avant triDenombrement : \n" + this); // affiche les éléments du tableau avant le tri par dénombrement
double debutTempsDenombrement = System.nanoTime ();
this.triDenombrement ();
double finTempsDenombrement = System.nanoTime ();
System.out.println ("tableau Denombrement apres triDenombrement : \n" + this); // affiche les éléments du tableau après le tri par dénombrement
afficherDuree ("Tri Denombrement", debutTempsDenombrement, finTempsDenombrement);
System.out.println ("nombre d'operations elementaires tri denombrement : " + operationElementaireDenombrement); // affiche la durée d'exécution du tri par dénombrement
} else { // retourne une erreur
System.out.println ("tableau Denombrement de taille <= 0"); // affiche une erreur
}
}
public String toString () { // affiche les éléments de l'objet courant et renvoit un String
StringBuilder stringBuilder = new StringBuilder ();
if (this.taille == 0) { // initialise la taille du tableau d'élément à 0
return "taille 0";
}
for (int i = 0; i < this.taille; i++) { // initialisation de la taille du tableau à 0
if (this.elements [i] == null) { // aucuns éléments de l'objet courant
stringBuilder.append (String.format ("%20s", "indice " + i + "=> null")).append ("\n");
} else { // éléments de l'objet courant
stringBuilder.append (String.format ("%20s", this.elements [i].getCle () + " => " + elements [i].getValeur ())).append ("\n");
}
}
return stringBuilder.toString ();
}
public void remplir (int grandeur) { // rempli le tableau avec des valeurs aléatoires
for (int i = 0; i < this.taille; i++) { // initialisation de la taille du tableau à 0
this.elements [i] = new Element (genereCle (grandeur), genereValeur ());
}
}
public void triBulle () { // tri le tableauElement avec le mode de tri à bulle
Element temporaire;
for (int i = 0; i < this.taille; i++) { // initialisation de la taille du tableau à 0
for (int j = 1; j < (this.taille - i); j++) { // initialisation de la taille du tableau à 1
if (elements [j - 1].getCle () > elements [j].getCle ()) { // permutation de la clé des éléments
temporaire = new Element (elements [j - 1]);
elements [j - 1] = elements [j];
elements [j] = temporaire;
operationElementaireBulle = operationElementaireBulle + 4;
}
}
}
}
public void triRapide (int debut, int fin) { // tri le tableau elements avec le mode de tri rapide avec des paramètres debut de l'indice, qui est le début du tableau et fin de l'indice, qui est la fin du tableau
if (debut < fin) { // si l'indice du début est avant la fin de l'indice du tableau, initialise la valeur de l'indice pivot
int indicePivot = partition (debut, fin);
triRapide (debut, indicePivot - 1);
triRapide (indicePivot + 1, fin);
operationElementaireRapide = operationElementaireRapide + 4;
}
}
public int partition (int debut, int fin) { // méthode appelée par triRapide pour échanger les éléments avec des paramètres debut de l'indice, qui est le début du tableau et fin de l'indice, qui est à la fin du tableau puis renvoit un int
Element valeurPivot = new Element (this.elements [debut]);
int d = debut + 1;
int f = fin;
operationElementaireRapide = operationElementaireRapide + 3;
while (d < f) { // l'indice du début est avant la fin de l'indice du tableau
while (d < f && this.elements [f].getCle () >= valeurPivot.getCle ()) { // l'indice de fin est après l'indice du pivot, on diminue l'indice de fin
f--;
operationElementaireRapide++;
}
while (d < f && this.elements [d].getCle () <= valeurPivot.getCle ()) { // l'indice de début est avant l'indice du pivot, on augmente l'indice du debut
d++;
operationElementaireRapide++;
}
Element temporaire = new Element (this.elements [d]);
this.elements [d] = this.elements [f];
this.elements [f] = temporaire;
operationElementaireRapide = operationElementaireRapide + 3;
}
if (this.elements [d].getCle () > valeurPivot.getCle ()) { // si l'indice de debut est après l'indice du pivot, on diminue l'indice du debut
d--;
operationElementaireRapide = operationElementaireRapide++;
}
this.elements [debut] = this.elements [d];
this.elements [d] = valeurPivot;
operationElementaireRapide = operationElementaireRapide + 2;
return d;
}
public void triDenombrement () { // tri le tableau avec le mode du tri dénombrement
int maximum = valeurMaximale (); // initialisation du maximum
Element [] reste = new Element [this.taille];
int [] tableauCompteur = new int [maximum + 1];
operationElementaireDenombrement = operationElementaireDenombrement + 4;
for (int i = 0; i < maximum; i++) { // initialisation du tableau de comptage à 0
tableauCompteur [i] = 0;
operationElementaireDenombrement++;
}
for (int i = 0; i < taille; ++i) { // comptage du nombre d'élements à la position éléments [i]
tableauCompteur [this.elements [i].getCle ()]++;
operationElementaireDenombrement++;
}
for (int i = 1; i <= maximum; ++i) { // comptage du nombre d'élements maximum à la position [i - 1]
tableauCompteur [i] += tableauCompteur [i - 1];
operationElementaireDenombrement++;
}
for (int i = 0; i < taille; ++i) { // comptage du nombre d'élements à la position éléments [i - 1]
reste [tableauCompteur [elements [i].getCle ()] - 1] = elements [i];
--tableauCompteur [elements [i].getCle ()];
operationElementaireDenombrement = operationElementaireDenombrement + 2;
}
for (int i = 0; i < taille; ++i) { // comptage du nombre d'élements restant à la position reste [i]
elements [i] = reste [i];
operationElementaireDenombrement++;
}
}
public int valeurMaximale () { // méthode pour chercher la valeur maximale dans un tableau et renvoit un int
int maximum = this.elements [0].getCle ();
for (int i = 1; i < this.taille; i++) { // initialisation du tableau à 1
if (this.elements [i].getCle () > maximum) { // cherche la cle de l'élément maximum
maximum = this.elements [i].getCle ();
}
}
return maximum;
}
} |
