/** TRI RAPIDE (Quick : rapide, Sort : tri) Fichier TriRapide1.java * Par Le Van N. pour IFT 1170 * * C'est une des applications connues de la récursivité : le tri rapide * Explication sur le Quick Sort : en classe * Il y a plusieurs versions de QuickSort comme il existe plein versions * du tri : l'importance est de comprendre au moins une et être capable * de l'utiliser comme il faut. * * Classe Date dans cet exemple : * - appel d'un constructeur sans paramètre : Date d = new Date(); * - utiliser la "redéfinition" de la méthode toString() redéfinie * dans cette classe Date (vs sa super classe Object) pour afficher * la date sous le format : (Wed Feb 11 13:36:17 EST 2015) * - utiliser la méthode getTime() dans la classe Date qui retourne * le nombre de millisecondes depuis le 1er Janvier 1970, 00:00:00 GMT * notre but est de calculer à peu près le temps du tri en millisecondes * * Dans l'exemple, on trie d'un tableau contenant environ de 150 000 entiers. * On compare avec la vitesse du tri par sélection (voir l'exécution à la fin du programme). */ import java.util.Date; // pour les méthodes de cette classe public class TriRapide1 { /* On crée un tableau des entiers : - contenant nbElem éléments - valeurs varient entre 0 et MAX_VAL (exclue) Math.random() retourne une valeur aléatoire (arbitraire) C'est une méthode statique de la classe Math */ static void creerAleatoire(int [] tableau, int nbElem, int MAX_VAL) { for (int i = 0 ; i < nbElem ; i++) tableau[i] = (int) ( MAX_VAL * Math.random()) ; } /* afficher PARTIELLEMENT le contenu du tableau : les 7 ers indices de 0 à 6, les 4 derniers On affiche des entiers alignés */ static void afficher(int [] tableau, String message) { System.out.println("Contenu partiel du tableau " + message); for(int i = 0 ; i < tableau.length ; i++) if ( i <= 6 || i >= tableau.length -4 ) System.out.printf("%6d) %8d\n", i, tableau[i]); else if (i == 7 ) System.out.println("etc .... "); System.out.println(); } /* partionner un tableau en deux sous tableaux : - placer la valeur du pivot à sa position finale (après le tri) - sa position finale est l'indice du pivot à retourner - en partionnant: les valeurs à gauche de l'indice du pivot <= valeur du pivot les valeurs à droite de l'indice du pivot > valeur du pivot vous n'avez pas besoin de comprendre techniquement cette fonction. Il faut retenir surtout son but. */ /* J'écris mais je n'appelle pas : Essayez de remplacer deux permutations dans partitionner par 2 appels de cette fonction et COMPARER le temps d'exécution. */ static void echanger(int T[], int g, int d) { int tempo = T[g]; T[g] = T[d]; T[d] = tempo; } static int partitionner ( int T[], int debut, int fin) { int g = debut , d = fin ; int valPivot = T[debut], tempo ; do { while ( g <= d && T[g] <= valPivot) g++; while ( T[d] > valPivot) d--; if ( g < d ) // echanger(T, g, d); { tempo = T[g]; T[g] = T[d]; T[d] = tempo; } } while ( g <= d ) ; // echanger(T, debut, d); tempo = T[debut]; T[debut] = T[d]; T[d] = tempo; return d; } /* Cette fonction est récursive car dans son corps on appelle cette même fonction (2 fois) */ static void quickSort ( int T[], int gauche, int droite ) { if (droite > gauche) /* au moins 2 éléments */ { int indPivot = partitionner ( T, gauche, droite); quickSort ( T, gauche, indPivot - 1 ); quickSort ( T, indPivot + 1, droite); } } static void trierSelection(int[] tableau, int nbElem) { for(int i = 0; i < nbElem-1; i++) { int indMin = i; for(int j = i+1; j < nbElem; j++) if (tableau[j] < tableau[indMin]) indMin = j; if (indMin != i) { int temp = tableau[i]; tableau[i] = tableau[indMin]; tableau[indMin] = temp; } } } static void trier(int nbElem, int genre) { int MAX_VAL = 1000000; /* valeurs varient entre 0 et un million */ int [] tableau = new int [nbElem]; if (genre == 1) System.out.println("Tri par sélection :\n"); else System.out.println("Tri rapide :\n"); creerAleatoire(tableau, nbElem, MAX_VAL); afficher(tableau, "apres la creation"); Date d = new Date(); long debut = d.getTime(); System.out.println("Debut du tri de " + nbElem + " entiers " + "(" + d.toString() + ")"); if (genre == 2) quickSort(tableau, 0, nbElem-1); else trierSelection(tableau, nbElem); d = new Date(); long fin = d.getTime(); System.out.println("Fin du tri de " + nbElem + " entiers " + "(" + d.toString() + ")"); System.out.println("Temps requis : " + (fin - debut) + " millisecondes "); afficher(tableau, "\nApres le tri"); } public static void main (String[] args) { final int MAX_ELEM = 151000, /* créer au maximum 151 000 entiers */ MINI_ELEM = MAX_ELEM - 1000; /* créer au minimum 150 000 entiers */ // un nombre aléatoire entre 150000 et 151000 int nbElem = (int)( (MAX_ELEM - MINI_ELEM + 1) * Math.random() + MINI_ELEM ); trier (nbElem, 1); trier (nbElem, 2); } } /* Exécution : --------------------Configuration: -------------------- Tri par sélection : Contenu partiel du tableau apres la creation 0) 247593 1) 68422 2) 811587 3) 824337 4) 916280 5) 943217 6) 515682 etc .... 150452) 202611 150453) 724788 150454) 755942 150455) 21842 Debut du tri de 150456 entiers (Wed Feb 11 13:35:58 EST 2015) Fin du tri de 150456 entiers (Wed Feb 11 13:36:17 EST 2015) Temps requis : 19243 millisecondes Contenu partiel du tableau Apres le tri 0) 0 1) 0 2) 1 3) 27 4) 37 5) 53 6) 55 etc .... 150452) 999988 150453) 999994 150454) 999994 150455) 999997 Tri rapide : Contenu partiel du tableau apres la creation 0) 12851 1) 730811 2) 283635 3) 60386 4) 696927 5) 369416 6) 760341 etc .... 150452) 873734 150453) 586753 150454) 687945 150455) 701018 Debut du tri de 150456 entiers (Wed Feb 11 13:36:17 EST 2015) Fin du tri de 150456 entiers (Wed Feb 11 13:36:17 EST 2015) Temps requis : 18 millisecondes Contenu partiel du tableau Apres le tri 0) 11 1) 11 2) 13 3) 15 4) 18 5) 39 6) 41 etc .... 150452) 999969 150453) 999971 150454) 999988 150455) 999995 Process completed. */