TD07 Tris
Télécharger le TD07 Tris en pdf
Page 1 : Pré-ING1Semestre 2 - 2024/2025Informatique IITD 7 : Tris de tableauxNe pas oublier de créer un répertoire pour placer les codes de ce TD !Toutes les fonctions écrites doivent être testées dans le programme principal !Pour ce TD et les suivants : les inclusions de bibliothèques, la déclaration des constantes ainsi que la déclaration destypes structurés si besoin, doivent être écrits dans un fichier .h qui doit être inclus dans votre fichier .c1Mise en place1. Définir une constante TAILLE de valeur 100.2. Déclarer dans le programme principal, un tableau d’entiers de taille 100 et le remplir avec des valeurs aléatoires entre0 et 500.3. Écrire/récuperer des TP précédents la procédureAfficheTableauint tab, int taille qui permet d’afficher letableau de taille TAILLE passé en paramètre.4. Écrire une fonction int tabTriint tab que retourne 1 si les éléments du tableau passé en paramètres sont triésdans l’ordre croissant.5. La fonction suivante permet de retourner le temps système en millisecondes. Si on appelle donc deux fois cette fonction,en début et en fin de code, on peut déterminer par différence le temps pris par la portion du programme pour s’exécuter.Le format d’affichage du type unsigned long est ld.ATTENTION : ne mettez pas d’instructions printf dans la portion de code que vous chronométrez car cela fausseragrandement la mesure : en effet, d’un point de vue du temps machine, l’affichage sur le terminal est une opérationextrêmement lente : prudence donc dans vos mesures.include sys/time.h // a inclure !unsigned long getTimeMilliSecstruct timeval tv;gettimeofday&tv,NULL;return 1000 tv.tvsec + tv.tvusec / 1000;2Programmation des tris lentsImplémenter un des tris lents parmi les 3 suivants.Mesurer le temps mis par la fonction et visualiser la variation de temps lorsque l’on multiplie TAILLE par 2 ou 4.1. En vous inspirant du cours, écrire une procédure void triSelectionint tab, int taille, qui trie le tableaupassé en paramètre avec la méthode du tri par sélection. Vérifier que ce tri fonctionne en utilisant le tableau et lesfonctions définies précédemment.2. En vous inspirant du cours, écrire une procédure void triBulleint tab, int taille, qui trie le tableau passéen paramètre avec la méthode du tri par sélection. Vérifier que ce tri fonctionne en utilisant le tableau et les fonctionsdéfinies précédemment.3. En vous inspirant du cours, écrire une procédure void triInsertionint tab, int taille, qui trie le tableaupassé en paramètre avec la méthode du tri par sélection. Vérifier que ce tri fonctionne en utilisant le tableau et lesfonctions définies précédemment.1
Page 2 : 3Implémentation des tris rapide.Implementer un des tris rapides parmis les deux çi-dessous.Mesurer le temps mis par la fonction et visualiser la variation de temps lorsque l’on multiplie TAILLE par 2 ou 4.1. Tris fusion :— En vous inspirant du cours, écrire une procédure void triFusionint tab, int taille qui trie le tableaupassé en paramètre avec la méthode du tri fusion. Vérifier que ce tri fonctionne.— Modifier le code précédent pour afficher le tableau à chaque étape du tri : à chaque passage dans la fonction etaprès chaque fusion pour observer les différentes étapes de l’algorithme.2. Tri rapide : L’algorithme de tri rapide du cours ne fonctionne que pour un tableau n’ayant pas de doublon dans seséléments. Modifier l’algorithme de remplissage du tableau afin que deux tableau ne puissent pas être égaux on pourrautiliser la fonction de recherche simple écrite au debut du TD.— En vous inspirant du cours, écrire une procédure void triRapideint tab, int taille, qui trie le tableaupassé en paramètre avec la méthode du tri rapide. Vérifier que ce tri fonctionne.— Modifier le code précédent pour afficher le tableau à chaque étape du tri après chaque partition pour observer lesdifférentes étapes de l’algorithme.4Recherche dans un tableau trié/non trié1. Écrire une fonction int RechercheTabint tab, int taille, int val qui parcourt le tableau passé en paramètreet retourne la valeur 1 si l’élement existe dans le tableau, la valeur 0 sinon.2. On rappelle qu’une recherche dichotomique est applicable sur un tableau préalablement trié. Elle se base sur le principesuivant :— on regarde l’élément central du tableau : s’il est plus petit que la valeur recherchée, alors cette dernière se trouvedans la seconde partie du tableau et inversement.— On recommence le processus précédent sur la moitié du tableau où l’on sait que se trouve l’élément recherché.— On procède ainsi jusqu’à trouver l’élément ou bien n’avoir plus qu’un tableau d’une seule case dans ce cas l’élémentrecherché n’existe pas dans le tableau.Écrire la fonction récursive int rechercheDicoint tab, int taille, int val, int debut, int fin qui re-cherche de manière dichotomique si val appartient au tableau passé en paramètre dont l’indice de départ est debut etl’indice final inclu est fin.La fonction retourne la valeur 1 si l’élement appartient au tableau, la valeur 0 sinon. Tester cette fonction.5Comparaison des recherches.1. Afficher le temps d’exécution d’une recherche simple non dichotomique ainsi que d’une recherche dichotomique pourla recherche du même élément dans le tableau tab.2. Recommencer en passant la valeur de TAILLE à 1000 puis à 10000. Quelle recherche est la plus efficace ?6Pour aller plus loin : le tri drapeau difficile !Le tri drapeau est un tri répondant à un problème bien particulier : réorganiser une collection d’éléments identifiés parleur couleur, sachant que seules trois couleurs sont présentes par exemple, rouge, blanc, bleu, dans le cas du drapeau desPays-Bas. Pour simplifier, nous allons utiliser des entiers plutôt que des couleurs, mais vous pouvez corser l’exercice enutilisant des énumérations.1. Définir un tableau d’entiers de taille 100 dont les éléments seront aléatoires entre 1 et 3 compris.2. Écrire une procédure TriDrapeauint tab, int taille qui prends en paramètre un tableau dont les éléments nepeuvent avoir que trois valeurs différentes et qui va le tier ainsi : tous les éléments 1 au début du tableau, puis les 2 puisles 3. Attention, on veut un vrai tri, c’est-à-dire qu’il ne faut pas compter le nombre d’occurrences de chaque élémentet redéfinir un nouveau tableau, mais bien échanger les éléments entre eux pour obtenir le tableau souhaité.Essayer d’obtenir une complexité en On.2
