Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

CHAPITRE V
Recherche et tri
Cherchez et vous trouverez, . . . car qui cherche trouve. Matthieu 7 7-8 et Luc 11 9-10
Objectif. Comprendrelestechniquesdebasepourorganiserdesdonn´eesordonne´es. Cechapitrediscutequelquesm´ethodesderechercheetdetri.Lesapplicationssontabondantes;imagi-nezparexempleaquelpointundictionnaireseraitdifcielautilisersilesmotscle´sn'´etaientpasordonn´es! Ils le sont, heureusement, car l'e´diteur a pris le soin de le s trier .Vousenprotezenappliquantunem´ethode efcace de recherche .Leprojetalandecechapitreillustreuneapplicationmions´evidente:larecherche dessolutionsd'une´equationdiophantienne(parexemple x 4 + y 4 + z 4 = w 4 avec x y z w Z + ). Sommaire 1.Recherchelin´eairevsrecherchedichotomique. 1.1.Recherchelin´eaire.1.2.Recherchedi-chotomique. 1.3. Attention aux de´tails ! 2.Troism´ethodesdetrie´l´ementaires. 2.1. Les plus petits exemples. 2.2. Tri par se´lection. 2.3. Tri par transposition. 2.4. Tri par insertion. 2.5. En sommes-nous contents ? 3. Diviser pour trier. 3.1. Le tri fusion. 3.2. Analyse de complexite. 3.3. Le tri rapide. 3.4. Ana-´ lyse de complexite´. 4.Fonctionsg´eneriques. 4.1.Lescalamit´esdelare´´ecritureinutile.4.2.L'usagedesfonctions ´ g´en´eriques.4.3.Imple´mentationderechercheettrienC++. 5. Solutions fournies par la STL. 5.1. Algorithmes de recherche et tri. 5.2. La classe ge´ne´rique set.5.3.Lesit´erateurs. Exemple 0.1. Lesdeuxproblemesfondamentaux,trietrecherche,peuvetnseformulerainsi: (1)Trierunelistedonn´eeand'´etablirl'ordre a 1 a 2 ≤    ≤ a n . (2)Chercherun´ele´ment b dans une liste ordonne´e ( a 1 a 2 ≤    ≤ a n ) . Ajoutonsqueletrir´esoutbiend'autresproblemesconcernantleslistes,apriorinontri´ees: (3)Trouverlese´l´ementsdoublesdansuneliste(problemedemultiplicite´). (4)Ve´riersideuxlistessontlesmˆemesapermutationpres(problemed'anagramme). (5)Trouverlam´edianed'unelonguelistedevaleursr´eelles(problemederang). Remarque 0.2 . D.E. Knuth dans The Art of Computer Programming discute diverses me´thodes de tri dans le tome 3, intitule´ Sorting and Searching . Tout au de´but il fait le constat suivant, toujours valable de nos jours : Computer manufacturers estimate that over 25% of the running time on their computers is cur-rently being spent on sorting (. . .) We may conclude that (i) there are many important applications of sorting, or (ii) many people sort when they shouldn't, or ( iii) inefcient sorting algorithms are in common use. The real truth probably involves some of all three alternatives. In any event we can see that sorting is worthy of serious study, as a practical matter. Cechapitretented'expliquerpuisdecomparerdiffe´rentesm´ethodesderecherche( § 1) et de tri ( § § 3). Lesexercicesmath´ematiquespermettrontd'e´tablirlacorrectiondesme´thodespropose´esetdecomparer leurperformance.Cettepartiepeutsemblerunpeuthe´oriquemaiselleesttresb´en´equepourcomprendre cequ'estl'algorithmique.Lamoralearetenir:pr´ef´ererlesbonsalgorithmesauxsolutionsna¨ves! + Si vous ˆetes impatient ou insouciant, vous pouvez lire la recherche dichotomique (algorithme V.2) puis letrifusion(algorithmeV.6)etletrirapide(algorithmeV.7),andepasserdirectemental'impl´ementation ( § 4). En § 5 nous regardons brievement quelles solutions offre la STL. 83