Une introduction aux l’algorithmes de tri

Une introduction aux l’algorithmes de tri

La compréhension des principaux algorithmes de tripasse obligatoirement par la compréhension du concept de base de ce que l’on entend par « algorithme ». Très utilisé en informatique, mais aussi en mathématiques, le terme « algorithme » désigne un ensemble d’instructions qui permet de résoudre n’importe quel problème mathématique. Cette technique est à la base de l’informatique car dans ce domaine, quasiment toutes les opérations et tâches exécutés manuellement (déplacement de souris, cliquer sur un lien, écrire, lire une vidéo etc…) ou automatiquement (ouverture d’un programme, tous les calculs effectués par l’appareil) relève d’un problème mathématique. Un grand nombre d’appareils fonctionnent sur le système des algorithmes : ordinateurs (des plus puissantes aux modèles les plus anciens), les téléphones portables, les machines à calculer etc…Par ailleurs, il existe autant de problèmes que d’algorithmes. Lorsque le problème consiste à organiser un ensemble d’objets dans un ordre bien déterminé, la résolution se fera grâce aux algorithmes de tri.

Les principaux algorithmes de tri

algorithmes-de-tri.jpg

En effet, contrairement aux algorithmes qui sont utilisés pour créer des évènements aléatoires, les algorithmes de trisont eux utilisés pour la création d’évènements ordonnés ou de relations d’ordre. D’où la notion de « tri ».Les algorithmes de triconstituent en eux-mêmes une grande famille, qui se subdivise suivant plusieurs critères dont le principe de résolution utilisé, la complexité, ou encore le caractère stable. D’où : les algorithmes d’application générale ou spécialisée, stables et instables etc…

Quelques exemples d’implémentations

implementations.jpg

Il existe plusieurs implémentations possibles pour un algorithme de tri.
Dans le cas de l’implémentation par insertion (généralement la plus simple), la technique consiste à insérer un élément à la place où il doit se trouver.
Implémenter un algorithme de tripar sélectionconsiste à ordonner les éléments dans un ordre croissant de façon à ce que le premier élément qui compose un vecteur soit le plus petit et ainsi de suite.
Dans une implémentation dite « à bulles », le tri se fera après avoir comparé les éléments deux à deux et en effectuant une permutation et renouveler l’opération jusqu’à ce quecelle-ci ne soit plus possible.