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
Domaines


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), ce qui signifie que dans le pire des cas, pour trier un tableau de n...

Cet article est réservé aux abonnés. Il vous reste 97% à découvrir.
à partir de 21,65€ HT/mois/lecteur pour un accès 5 lecteurs à toute la plateforme
J'en profite


Articles qui pourraient vous intéresser...

Utiliser Visual Studio Code pour coder en Python

Magazine
Marque
GNU/Linux Magazine
Numéro
243
Mois de parution
décembre 2020
Domaines
Résumé

Comme Batman a Robin, Rocket Raccoon a Groot, le développeur a l’éditeur de code. Sans son plus fidèle acolyte, impossible d’écrire la moindre ligne de code... d’où l’importance d’être toujours à la recherche de l’outil le plus efficace qui soit, quitte à délaisser un vieux compagnon de route...

Générez la documentation technique de vos projets Godot

Magazine
Marque
GNU/Linux Magazine
Numéro
243
Mois de parution
décembre 2020
Domaines
Résumé

Découvrons comment utiliser GDScript Docs Maker pour générer automatiquement la documentation de vos projets Godot. Nous allons voir dans cet article que l’on peut simplement, à partir de notre code et de ses commentaires, avoir une documentation toujours à jour.