Cliquez ici pour retirer la feuille de style si vous souhaitez imprimer ce document (ou en cas de problème d'affichage).

Manipulation et tris de tableaux d'entiers

Pour s'échauffer

Pour se mettre en route, commencez par faire une fonction mirroir() qui inverse les éléments d'un tableaux d'entiers (par exemple le tableau 1,2,3,4,5 devient 5,4,3,2,1).

Tri dichotomique

Le but ici est de de trier un tableau d'entiers par une méthode dichotomique. Ecrivez une fonction int place_premier(int tab[], int taille); qui suivra les étapes suivantes :
  • on note x la valeur du premier élément, et on parcourt le début du tableau à la recherche du premier élément plus grand que x. On sauvegarde son indice dans une variable ppg (premier plus grand). Si x était le plus grand élément du tableau, la variable ppg doit valoir taille à la fin de cette étape.
  • on continue le parcourt du tableau à partir de l'indice ppg+1, et chaque fois qu'on trouve un élément plus petit ou égal à x, on l'échange avec la case ppg et on incrémente la variable ppg.
  • lorsque la fin du tableau est atteinte, on échange la case 0 (x) avec la case ppg-1.
  • la fonction retourne le nouvel indice de x, c'est a dire ppg-1
En principe, après l'appel à cette fonction le tableau est maintenant composé de tous les éléments plus petits ou égaux à x, puis de x, puis uniquement d'élements plus grand que x. Ecrivez maintenant une fonction void tri_dicho(int tab[], int taille); qui suit les étapes suivantes :
  • Si le tableau a une taille inférieure ou égale à 1, c'est fini. Sinon,
  • appel de place_premier() sur la totalité du tableau, on récupère la valeur renvoyée dans une variable p
  • appel de tri_dicho() sur la partie gauche, c'est à dire le tableau allant de l'indice 0 à l'indice p-1
  • appel de tri_dicho() sur la partie droite, c'est à dire le tableau allant de l'indice p+1 à l'indice taille-1.

Tri à bulles

En vous aidant uniquement de cette page wikipedia codez une fonction de tri utilisant l'algorithme du tri à bulles (simple d'abord puis optimisé). Vous utiliserez votre fonction swap() du tp4

Tri rapide

En vous aidant uniquement de cette page wikipedia codez une fonction de tri utilisant l'algorithme du tri rapide. Vous utiliserez votre fonction swap() du tp4