next up previous
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".

  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 :

\begin{displaymath}\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 \end{displaymath}

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 :

\begin{displaymath}5,~9,~1,~5,~2,~8,~3,~5,~15,~3,~1\end{displaymath}

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 :

Utiliser les trois remarques précédentes pour écrire un algorithme améliorant le tri à bulle. Ce tri s'appelle tri shaker.


next up previous
suivant: À propos de ce
Maylis Delest 2005-04-06