Remerciez-le!

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

Introduction Cette méthode de tri, probablement la plus utilisée actuellement —

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 1960. 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 sous- problè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 effectue 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 suffit 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. Dans 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). uploads/S4/ expose-tri.pdf