Dans la suite, vous utiliserez le fichier Chronometre.java afin de mesurer le temps d'exécution de certains programmes. Pour mesurer le temps d'exécution d'un programme, créez une variable de type Chronometre, appelez la fonction start sur cette variable, exécutez la fonction dont vous souhaitez mesurer le temps, puis appelez la fonction stop du chronomètre : cette fonction renvoie le temps qui s'est écoulé depuis l'appel de la fonction start en ms :

 

Chronometre j =new Chronometre(); j.start(); //Appelez ici une fonction à tester long duree = j.stop();

1) Voici la classe Main : dans la fonction main, un tableau est créé (dont vous devez fixer le nombre de cases) et rempli avec des entiers tirés au hasard... La fonction verificateur permet de vérifier si un tableau est trié.

 

import java.util.Random; public class Main {     public static void main(String[] args)     {         int taille;         int[] tab;         Random r = new Random();         taille=20;         tab=new int[taille];         for(int i = 0; i<tab.length; i=i+1)         {             tab[i] = r.nextInt();         }     }     public static void verificateur(int[] T)     {         boolean good = true;         for(int i=0; i<T.length-1; i++)         {             if(T[i] > T[i+1])             {                 good=false;                 break;             }         }                 if(good)         {             System.out.println("Le tableau est trie");         }         else         {             System.out.println("Le tableau n'est PAS trie!!");         }     } }

Complétez ce code pour construire un tableau de 30 cases et l'afficher à l'écran. Le tableau est-il trié ? Et que dit la fonction verificateur ?

2) Ecrivez une fonction qui prend un tableau en paramètre et le trie. Cette fonction devra rechercher dans le tableau le plus grand élément, et le placer à la fin, puis recommencer avec le second plus grand élément, etc.

 Testez cette fonction sur le tableau créé précédemment : le tableau doit être trié à la fin de votre fonction (vérifiez que c'est le cas).

3) Utilisez le chronomètre pour mesurer le temps d'exécution de votre fonction sur des tableaux de taille 20, 40, 60, 80, 100, 120 et 140 milles cases. Utilisez un tableur (excel, openoffice, ...) ou ce site web pour tracer la courbe représentant le temps d'exécution de votre fonction en fonction du nombre de cases du tableau. A quoi ressemble la courbe obtenue ? N'oubliez pas d'utilisez verificateur afin de vous assurer que votre fonction a bien trié les tableaux.

4) Nous allons maintenant coder le tri fusion, afin de voir s'il est plus rapide. Voici le pseudo code du tri fusion :

fonction trifusion (tableau T, entier debut, entier fin)     Si le tableau T, restreint aux cases situées entre les cases debut (incluse) et fin (incluse aussi), fait plus d'une case      |      |  milieu = moyenne entre fin et debut      |  trifusion(T, debut, milieu);      |  trifusion(T, milieu+1, fin);      |  fusion(T, debut, milieu+1, fin); fonction fusion (tableau T, entier debut, entier milieu, entier fin)     creer un nouveau tableau P de (fin-debut+1) cases.     i = debut;     j = milieu;         Pour k parcourant toutes les cases de P      |      |  Si i est strictement plus petit que milieu et que j est plus petit ou égal à fin      |   |       |   |  Si l'entier à la case i du tableau T est plus petit que l'entier à la case j      |   |   |  placer l'entier à la case i du tableau T dans la case k du tableau P      |   |   |  incrémenter i;      |   |  Sinon      |   |   |  placer l'entier à la case j du tableau T dans la case k du tableau P      |   |   |  incrémenter j;      |      |  Sinon, si i est plus grand ou égal à milieu      |   |      placer l'entier à la case j du tableau T dans la case k du tableau P      |   |      incrémenter j;      |      |  Sinon      |   |      placer l'entier à la case i du tableau T dans la case k du tableau P      |   |      incrémenter i;     Recopier toutes les cases du tableau P dans les cases du tableau T à partir de la case debut

Testez cette fonction sur un petit tableau (30 cases) et vérifiez qu'elle fonctionne (pour lancer le tri, appelez la fonction trifusion sur le tableau, entre les cases 0 et (taille du tableau -1)). Répétez les mesures effectuées à la question 3.

Dans la suite, nous allons tester les fonctions de recherche d'éléments dans le tableau. Comme ces fonctions sont beaucoup plus rapides qu'un tri, il faudra utiliser ChronometreMicro.java, qui permet d'obtenir une mesure en microseconde du temps d'exécution d'un algorithme.

1) Le code réalisé dans la partie précédente permet de générer un tableau au hasard, et de le trier. Vous allez devoir le réutiliser pour la suite.

Ecrivez une fonction prenant en paramètre un tableau et un entier, et qui recherche si l'entier est dans le tableau en parcourant tout le tableau du début à la fin. Si l'entier est trouvé, la fonction renvoie la position de l'entier dans le tableau. Sinon, elle renvoie -1. Testez cette fonction sur un petit tableau, en recherchant un élément qui soit dans le tableau et un élément qui ne soit pas dans le tableau (affichez à chaque fois le tableau à l'écran pour vérifier que ça a fonctionné).

Mesurez les temps d'exécution de votre fonction sur des tableaux de taille 100, 200, 300, 400 et 500 milles cases (en demandant à rechercher, dans le tableau, le nombre 2183). Tracez la courbe représentant le temps d'exécution en fonction du nombre de cases. A quoi ressemble la courbe obtenue ? Attention, excluez la fonction de tri du tableau du temps de calcul...

2) Faites de même en utilisant la fonction de recherche dichotomique vue en TD. Que constatez-vous ?