Les algorithmes de tri font partie des grands classiques de l'informatique. Vous avez tous dû aborder à un moment ou à un autre au moins l'un de ces algorithmes. Je vous propose de voir ou revoir certains d'entre eux sous un angle un peu original, en étudiant les effets que vont avoir les langages que vous allez choisir et la manière dont vous allez les coder.
Un algorithme de tri effectue une tâche simple : on lui donne en entrée des données dans un ordre quelconque et on obtient en sortie les données ordonnées (ordre numérique ascendant ou descendant, ordre alphabétique, etc.). Nous considérerons dans cet article que nous souhaitons trier un tableau unidimensionnel contenant des données numériques (entiers) et bien sûr, nous n'aborderons que quelques-uns des nombreux algorithmes de tri existants. Nous verrons ensuite que suivant le langage utilisé et suivant la façon d'implémenter un algorithme, les performances pourront être significativement différentes !
1. Quelques algorithmes de tri
Commençons par effectuer ce qui devrait être normalement un rappel de quelques algorithmes permettant de trier des données.
1.1 Le tri à bulles
Le tri à bulles est un algorithme de tri très simple et peu efficace. Sa complexité est en O(n2), ce qui signifie que dans le pire des cas, pour trier un tableau de n...
- Accédez à tous les contenus de Connect en illimité
- Découvrez des listes de lecture et des contenus Premium
- Consultez les nouveaux articles en avant-première