Previous Next Up Index Contents

d) Tris de tableaux



Exercice 10.17 Tri de Shell

Traduire la fonction TRI_SHELL définie ci-dessous en C. Utiliser la fonction PERMUTER définie dans le cours.

Ecrire un programme profitant des fonctions définies dans les exercices précédents pour tester la fonction TRI_SHELL.

   procédure TRI_SHELL(T,N)
   |  (* Trie un tableau T d'ordre N par la méthode
   |     de Shell en ordre croissant. *)
   |  résultat: entier tableau T[100]
   |  donnée: entier N
   |  entier SAUT, M, K
   |  booléen TERMINE
   |  en SAUT ranger N
   |  tant que (SAUT>1) faire
   |  |  en SAUT ranger SAUT divent 2
   |  |  répéter
   |  |  |  en TERMINE ranger vrai
   |  |  |  pour M variant de 1 à N-SAUT faire
   |  |  |  |  en K ranger M+SAUT
   |  |  |  |  si (T[M]>T[K]) alors 
   |  |  |  |  |   PERMUTER(T[M],T[K])
   |  |  |  |  |   en TERMINE ranger faux
   |  |  |  |  fsi
   |  |  |  fpour
   |  |  jusqu'à TERMINE
   |  ftant (* SAUT <= 1 *)
   fprocédure (* fin TRI_SHELL *)

Remarque: L'algorithme a été développé par D.L.Shell en 1959. En comparant d'abord des éléments très éloignés, l'algorithme a tendance à éliminer rapidement les grandes perturbations dans l'ordre des éléments. La distance entre les éléments qui sont comparés est peu à peu réduite jusqu'à 1. A la fin du tri, les éléments voisins sont arrangés.


Exercice 10.18

Déterminer le maximum de N éléments d'un tableau TAB d'entiers de trois façons différentes:

a) la fonction MAX1 retourne la valeur maximale

b) la fonction MAX2 retourne l'indice de l'élément maximal

c) la fonction MAX3 retourne l'adresse de l'élément maximal

Ecrire un programme pour tester les trois fonctions.


Exercice 10.19 Tri par sélection

Ecrire la fonction TRI_SELECTION qui trie un tableau de N entiers par la méthode de sélection directe du maximum (voir exercice 7.14). La fonction fera appel à la fonction PERMUTER (définie dans le cours) et à la fonction MAX3 (définie dans l'exercice précédent).

Ecrire un programme pour tester la fonction TRI_SELECTION.


Exercice 10.20

Ecrire la fonction INSERER qui place un élément X à l'intérieur d'un tableau qui contient N éléments triés par ordre croissant, de façon à obtenir un tableau à N+1 éléments triés par ordre croissant. La dimension du tableau est incrémentée dans la fonction INSERER.

Ecrire un programme profitant des fonctions définies plus haut pour tester la fonction INSERER.


Exercice 10.21 Tri par insertion

Ecrire la fonction TRI_INSERTION qui utilise la fonction INSERER pour trier par ordre croissant les éléments d'un tableau à N éléments.

Ecrire un programme pour tester la fonction TRI_INSERTION.

Méthode: Trier le tableau de gauche à droite en insérant à chaque fois l'élément I+1 dans le tableau (déjà trié) des I premiers éléments.


Exercice 10.22

Ecrire la fonction RANGER qui arrange le contenu de ses deux paramètres X et Y de façon à ce que le contenu de X soit plus petit que celui de Y. RANGER retourne la valeur logique 1 si un échange a eu lieu, sinon 0.


Exercice 10.23 Tri par propagation

Ecrire la fonction TRI_BULLE qui trie un tableau de N éléments entiers par ordre croissant en appliquant la méthode de la bulle (tri par propagation - voir exercice 7.15). Employer la fonction RANGER de l'exercice ci-dessus.

Ecrire un programme pour tester la fonction TRI_BULLE.


Exercice 10.24 Fusion de tableaux triés

Ecrire la fonction FUSION qui construit un tableau FUS trié par ordre croissant avec les éléments de deux tableaux A et B triés par ordre croissant. Pour deux tableaux de dimensions N et M, le tableau FUS aura la dimension N+M. (Méthode: voir exercice 7.13)

Ecrire un programme qui teste la fonction FUSION à l'aide de deux tableaux lus au clavier et triés à l'aide de TRI_BULLE.


Previous Next Up Index Contents


Feedback - Copyright © 1993,1996,1997 F.Faber