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