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".

1. Décrire une recherche dichotomique sur ce tableau pour chacun des mots suivants :
   "émilie", "aimé", "émile", "william"
2. Écrire un fonction récursive recherche_dichotomique_rec pour un tableau T. Tester votre fonction avec le tableau précédent.
3. Écrire un fonction itérative recherche_dichotomique_iter pour un tableau T. Tester votre fonction avec le tableau précédent.
4. 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 :

$$\frac{1}{4},~\frac{4}{3},~\frac{1}{7},~\frac{3}{4},~\frac{1}{2},~\frac{17}{3},~\frac{4}{8},~-\frac{3}{5},\frac{3}{5},~0$$

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 :

$$5,~9,~1,~5,~2,~8,~3,~5,~15,~3,~1$$

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 $5,7,9, 3$ est trié en une passe, mais le tableau contenant $9, 3, 5, 7$ 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.