Algorithmes de tri et impacts des choix d'implémentation sur les performances

Magazine
Marque
GNU/Linux Magazine
Numéro
176
Mois de parution
novembre 2014
Spécialité(s)


Résumé

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

La suite est réservée aux abonnés. Il vous reste 97% à découvrir.
  • 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
Envie de lire la suite ? Rejoignez Connect
Je m'abonne maintenant


Article rédigé par

Par le(s) même(s) auteur(s)

Édito

Magazine
Marque
GNU/Linux Magazine
Numéro
255
Mois de parution
janvier 2022
Résumé

Dans des temps anciens, les logiciels propriétaires et les logiciels open source se menaient une guerre sévère. Ces temps-là sont désormais révolus. On ne peut pas dire que l’un ou l’autre bord ait gagné, mais en tout cas, il n’existe plus de tension aussi forte entre les partisans des deux camps. On peut se dire que c’est l’open source qui a gagné, qui a finalement été accepté. Mais c’est sans doute oublier un peu vite que l’on peut établir une distinction entre logiciel open source et logiciel libre, le premier profitant de la philosophie du second à des fins purement pécuniaires.

Jouons avec le bytecode Python !

Magazine
Marque
GNU/Linux Magazine
Numéro
255
Mois de parution
janvier 2022
Spécialité(s)
Résumé

Comme tout développeur Python le sait (en tout cas, il faut l'espérer), Python est un langage semi-interprété compilé dans un pseudo-code, le bytecode, et exécuté dans une machine virtuelle. Voyons dans cet article comment le modifier à la volée.

Les listes de lecture

Python niveau débutant

9 article(s) - ajoutée le 01/07/2020
Vous désirez apprendre le langage Python, mais ne savez pas trop par où commencer ? Cette liste de lecture vous permettra de faire vos premiers pas en découvrant l'écosystème de Python et en écrivant de petits scripts.

Au pays des algorithmes

11 article(s) - ajoutée le 01/07/2020
La base de tout programme effectuant une tâche un tant soit peu complexe est un algorithme, une méthode permettant de manipuler des données pour obtenir un résultat attendu. Dans cette liste, vous pourrez découvrir quelques spécimens d'algorithmes.

Analyse de données en Python

10 article(s) - ajoutée le 01/07/2020
À quoi bon se targuer de posséder des pétaoctets de données si l'on est incapable d'analyser ces dernières ? Cette liste vous aidera à "faire parler" vos données.
Plus de listes de lecture