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;
}
} |
Partager