suivant: À propos de ce
Université Bordeaux 1 Licence Informatique 2004/2005 
Initiation à l'algorithmique 
 
TD 7
Dans les exercices qui suivent on manipule des tableaux de taille
NMAX et on veut les trier dans l'ordre croissant.
Exercice 7.1Recherche dichotomique
On considère un tableau T contenant les chaînes de caractères suivantes (triées dans l'ordre lexicographique) :
  "alain", "alexandra", "alfred", "émilie", "ernest", "jules", "julie", "laetitia" , "patrice", "xavière".
- Décrire une recherche dichotomique sur ce tableau pour chacun des mots suivants :
    "émilie", "aimé", "émile", "william"
 
- Écrire un fonction récursive 
recherche_dichotomique_rec pour un tableau T.
    Tester votre fonction avec le tableau précédent.
 
- Écrire un fonction itérative 
recherche_dichotomique_iter pour un tableau T.
    Tester votre fonction avec le tableau précédent.
 
- Déterminez la complexité de l'algorithme de recherche dichotomique.
  
 
Exercice 7.2Tri fusion
Faire tourner l'algorithme de  tri Fusion sur le tableau de rationnels suivant :
  
Quelle est la complexité de cet algorithme ?
  Étudiez le cas d'un tableau déjà trié, d'un tableau trié en ordre décroissant.
  Ce tri est-il stable ?
Exercice 7.3Tri Rapide
Faire tourner l'algorithme de tri Rapide sur le  tableau d'entiers suivant :
    
Quelle est la complexité de cet algorithme ?
    Étudiez le cas d'un tableau déjà trié, d'un tableau trié en ordre décroissant.
    Ce tri est-il stable ?
Exercice 7.4
On considère la structure :
   type élève=structure
     présence:booleen;
     note : entier;
     nom : chaîne de caractères
   finstructure
  et un tableau tableauEleve de n élèves.
Comment modifier la fonction précédente pour que celle-ci puisse s'appliquer aussi
  bien à un tri par nom qu'à un tri par note ?
  Quel tri utiliser pour trier sur la présence ?
Exercice complémentaire
Exercice 7.5Tri shaker
Pour améliorer le tri à bulle, on peut faire les modifications suivantes :
- limiter les parcours sans échanges.
 
- mémoriser le plus grand indice à partir duquel les échanges ne se font plus,
    c'est à dire l'indice en dessous du quel la liste est triée.
 
- alterner les sens des parcours consécutifs afin de traiter
    le cas où les éléments mal placés se trouvent en début de tableau.
par exemple, dans un tri à bulle, le tableau qui contient 
 est trié en une passe, mais le tableau
    contenant 
 est trié en 3 passes.
  
 
  
  Utiliser les trois remarques précédentes pour écrire un algorithme améliorant le tri à bulle. Ce tri s'appelle tri shaker.
 
 
   
 suivant: À propos de ce
Maylis Delest
2005-04-06