Exercice 1 : tri à bull 

Le tri à bulles est un algorithme de tri qui consiste à faire remonter progressivement les plus grands éléments d’un tableau (comme des bulles d’air remontent à la surface d’un verre de champagne). Le tri à bulles est une succession d’étapes. Une étape du tri à bulles consiste à parcourir tous les éléments du tableau et à échanger dans le tableau l’élément courant avec l’élément suivant si l’élément courant est strictement plus petit que l’élément suivant. Par un exemple, voici ce que donne le tri à bulles sur la liste [5,1,3,7,2] : Première étape :

5, 1, 3, 7, 2] → [1, 5, 3, 7, 2] → [1, 3, 5, 7, 2] → [1, 3, 5, 7, 2] → [1, 3, 5, 2, 7]

Deuxième étape :

[1, 3, 5, 2, 7] → [1, 3, 5, 2, 7] → [1, 3, 5, 2, 7] → [1, 3, 2, 5, 7]

Troisième étape :

[1, 3, 2, 5, 7] → [1, 3, 2, 5, 7] → [1, 2, 3, 5, 7]

Quatrième étape :

[1, 2, 3, 5, 7] → [1, 2, 3, 5, 7]

-          Écrire un algorithme tri_a_bulles qui implémente le tri à bulles.

-          Calculer la complexité de cet algorithme.

-          Traduit votre algorithme en un programme c.

Exercice 2 : tri par sélection

Sur un tableau de n éléments (numérotés de 0 à n-1), le principe du tri par sélection est le suivant :

— rechercher le plus petit élément du tableau, et l’échanger avec l’élément d’indice 0 ;

— rechercher le plus petit élément de la portion du tableau comprise entre les indices 1 et n-1, et l’échanger avec l’élément d’indice 1 ;

— rechercher le plus petit élément de la portion du tableau comprise entre les indices 2 et n-1, et l’échanger avec l’élément d’indice 2 ;

— continuer de cette façon jusqu’à ce que le tableau soit entièrement trié.

Écrire un algorithme de tri_par selection qui tri le tableau t en utilisant le tri par sélection. Tester votre procédure sur plusieurs exemples?

Calculer la complexité asymptotique de cet algorithme ?

Exercice 3 : tri par insertion

Le tri par insertion permet de trier une liste L d’éléments. Il consiste à ajouter un à un les éléments de L dans une liste R initialement vide, de sorte que la liste R soit toujours triée. Implémenter la fonction tri_insertion(t) qui prend en paramètre un tableau t et qui renvoie un nouveau tableau trié contenant les éléments de t. Tester l’algorithme sur la liste [2,7,1,2,8,7,5]. Implémenter une procédure tri_insertion_en_continu() qui demande à l’utilisateur des entiers, qui affiche au fur et à mesure la liste triée des entiers tapés par l’utilisateur et qui s’arrête quand l’utilisateur tape -1.

Exercice 4 : tri rapide

Le principe du tri rapide consiste à choisir un élément p du tableau, appelé pivot, puis à trier le tableau en mettant les éléments plus petits que p à gauche de p et les éléments plus grands que p à droites de p. Ensuite, on recommence le processus sur le tableau de gauche d’une part (c’est à dire les éléments situés à gauche du pivot) et sur le tableau de droite d’autre part. L’algorithme s’arête quand le tableau est complètement trié.

-          Écrire un algorithme tri_rapide qui implémente le tri à rapide.

-          Calculer la complexité de l’algorithme ?

-          Traduit l’algorithme en programme c

Exercice 5 : tri par fusion

Le tri fusion consiste à couper le tableau en 2 de tailles identiques (à un élément près), à trier le tableau de gauche en utilisant l’algorithme de tri fusion, à trier le tableau de droite avec le même algorithme, puis à fusionner les deux tableaux.

-          Écrire un algorithme qui implémente le tri fusion.

-          Calculer la complexité de l’algorithme

-          Traduit l’algorithme en un programme c

Exercice 6 : tri par shell

Il est généralement appliquer sur les tableaux qui ont une grande taille et Basée sur le calcul du pas et comment utiliser le pas. 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 réduite jusqu'à 1. A la fin du tri, les éléments voisins sont arrangés.

-          Ecrire un algorithme qui implimente le tri par shell

-          Calculer la complexité de l’algorithme

-          Traduit cet algorithme en un programme c