Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Expose tri Introduction Cette méthode de tri probablement la plus utilisée actuellement ?? d ? aucuns disent même que c ? est l ? algorithme le plus utilisé au monde ?? a été inventée par Sir Charles Antony Richard Hoare en Elle illustre le principe dit d

Introduction Cette méthode de tri probablement la plus utilisée actuellement ?? d ? aucuns disent même que c ? est l ? algorithme le plus utilisé au monde ?? a été inventée par Sir Charles Antony Richard Hoare en Elle illustre le principe dit diviser pour régner ? qui consiste à appliquer récursivement une méthode destinée à un problème de taille donnée à des sousproblèmes similaires mais de taille inférieure Ce principe général produit des algorithmes qui permettent souvent d ? importantes réductions de complexité La stratégie de l ? algorithme de tri rapide quicksort consiste dans un premier temps à diviser le tableau en deux parties séparées par un élément appelé pivot de telle manière que les éléments de la partie de gauche soient tous inférieurs ou égaux à cet élément et ceux de la partie de droite soient tous supérieurs à ce pivot dans l ? algorithme donné ci-dessus la partie qui e ?ectue cette t? che est appelée partition Ensuite d ? une manière récursive ce procédé est itéré sur les deux parties ainsi crées Notez que qu ? au départ le pivot est choisi dans la version de ci-dessus comme le dernier élément du tableau Choix du pivot Le choix idéal serait que ça coupe le tableau exactement en deux parties égales Mais cela n ? est pas toujours possible On peut prendre le premier élément Mais il existe plusieurs autres stratégies Partitionnement on parcourt le tableau de gauche à droite jusqu'à rencontrer un élément supérieur au pivot on parcourt le tableau de droite à gauche jusqu'à rencontrer un élément inférieur au pivot on échange ces deux éléments et on recommence les parcours gauche-droite et droite-gauche jusqu'à a avoir il su ?t alors de mettre le pivot à la frontière par un échange D Complexité Nous donnons les résultats classiques et connus mathématiquement pour les démonstrations nous renvoyons aux ouvrages de R Sedgewick Aho-Ullman cités dans la bibliographie L'opération élémentaire choisie est la comparaison de deux cellules du tableau Comme tous les algorithmes qui divisent et traitent le problème en sous-problèmes le nombre moyen de comparaisons est en O n log n que l'on nomme complexité moyenne L'expérience pratique montre que cette complexité moyenne en O n log n n'est atteinte que lorsque les pivots successifs divisent la liste en deux sous-listes de taille à peu près équivalente CDans le pire des cas par exemple le pivot choisi est systématiquement à chaque fois la plus grande valeur on montre que la complexité est en O n ? Comme la littérature a montré que ce tri était le meilleur connu en complexité il a été proposé beaucoup d'améliorations permettant de choisir un pivot le meilleur possible des combinaisons avec d'autres tris par insertion généralement si le tableau à trier est trop petit etc Ce tri est pour nous un excellent exemple illustrant la récursivité et en outre un exemple de tri en n log n C