Discussion :

[MultiT4sker]

Salut à tous,
J'ai commencé à lire le livre Introduction à l'algorithmique 2nde édition de Thomas Cormen.
J'ai remarqué que les algorithmes de tris y prennent une grande place. Dans le livre, ils expliquent qu'ils sont très utilisés dans les problèmes modernes.
J'aimerais bien savoir dans quel types de problèmes ils sont utilisés car quand j'y prendre je n'en vois pas trop.
J'ai fais une petite recherche mais pas de réponses à ma question.
Merci.

[DonQuiche]

Bonjour.

Pour commencer, ils sont utilisés chaque fois que tu veux afficher un résultat trié à l'utilisateur, que ce soit fait par la DB ou par ton code proprement dit.

Ensuite il y a tout un tas de problème où l'on souhaite obtenir les résultats entre telle et telle valeur, souvent pour des raisons d'optimisation (uniquement afficher N éléments parmi M). Dans un tel cas une liste triée couplée à une recherche dichotomique est une solution simple et efficace.

Au-delà de ça les tris sont les composants d'autres algorithmes, par exemple les aproches "best fit" dans les problèmes de bin packing et strip packing : on cherche à optimiser la disposition des colis dans un conteneur ou des images sur une page. Pour ça on prend à chaque étape le plus grand élément possible en les piochant depuis une structure triée.

Ou encore comment comparer deux listes pour trouver leurs différences ? Dans bien des cas un tri in-place des deux listes suivi d'une comparaison deux-à-deux des éléments est la bonne solution.


Tout cela étant dit, en pratique on utilise des algorithmes tous faits et il suffit d'en avoir deux, un quicksort en un tri stable, et de savoir quand utiliser le second plutôt que le premier. La connaissance des structures de recherche (liste triée, arbre binaire, hashmap, etc) est plus utile à mon avis.

[MultiT4sker]

Merci pour ta réponse, tu m'as bien éclairé.
Je pensais que ça servait seulement à trier des valeurs mais je me doutais qu'il existait d'autre domaines d'application.

[voblivion]

Plus en profondeur et plus abstraitement à la fois, j'ajouterai que l'étude des algorithmes de tri, qui sont très divers et très complexes sans trop l'être, sont un bon moyen pour se muscler l'esprit et apprendre à réfléchir différemment en informatique.

vob