TD n°5 : Les tris

TD n5 Les tris Le tri est sans doute le problme fondamental de lalgorithmique 1 plus de 25 des cycles CPU sont dans les tris 2 le tri est fondamental beaucoup dautres problmes Ainsi donc aprs le tri beaucoup de problmes deviennent faciles rsoudre Exercice 1 Tri par slection Principe Pour une place donne i on slectionne llment qui doit y tre positionn Pour trier le sous-tableau ti tn il suffit de positionner au rang i le plus petit lment de ce sous-tableau et de trier le sous-tableau ti1 tn Exemple

Exercice 2 Tri bulles Principe La stratgie de cet algorithme est comme suit Slectionner le minimum du tableau en parcourant le tableau de la fin au dbut et en changeant tout couple dlments conscutifs non ordonns Exemple Exercice 3 Tri par insertion par permutation Principe Dans ce cas itrativement nous insrons le prochain lment dans la partie qui est dj trie prcdemment La partie de dpart qui est trie est le premier lment En insrant un lment dans la partie trie il se pourrait quon ait dplacer plusieurs autres Exemple

Exercice 4 Tri par comptage Le tri par comptage consiste pour chaque lment du tableau compter combien dlment sont plus petit que lui grce ce chiffre on connat la position dans le tableau rsultat Exemple Tab 42 20 17 13 28 14 23 15 Nbinfrieur

7 4 3 6 1 5 2 Tab ordonn 13 14 15 17 20 23 28 42