Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Algorithmes de tri : Méthodes de tri et comparaison

Dans cours

CS-119(d): Information, calcul, communication

L'objectif de ce cours est d'introduire les étudiants à la pensée algorithmique, de les familiariser avec les fondamentaux de l'Informatique et de développer une première compétence en programmation (langage C++). ...

Description

Cette séance de cours porte sur l'importance des méthodes de tri dans la pratique, car elles sont essentielles pour une recherche efficace et sont utilisées dans divers algorithmes.

Enseignant·e

Jean-Cédric Chappelier

Jean-Cédric Chappelier est ingénieur diplômé et docteur de l'Ecole Nationale Supérieure des Télécommunications de Paris. Il est actuellement collaborateur scientifique et chargé de cours à l'Ecole Polytechnique Fédérale de Lausanne où il participe à l'activité de recherche et enseigne, entre autres, dans le domaine du traitement automatique des langues.

Source officielle

Proximité ontologique

Informatique théorique

Algorithmes et structures de données: Analyse de la complexité des algorithmes

Concepts associés (32)

Algorithme de tri

Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée. Les objets à trier sont des éléments d'un ensemble muni d'un ordre total. Il est par exemple fréquent de trier des entiers selon la relation d'ordre usuelle « est inférieur ou égal à ». Les algorithmes de tri sont utilisés dans de très nombreuses situations. Ils sont en particulier utiles à de nombreux algorithmes plus complexes dont certains algorithmes de recherche, comme la recherche dichotomique.

Réseau de tri

thumb|Un réseau de tri simple composé de quatre fils et cinq connecteurs. En Informatique, un réseau de tri est un algorithme de tri qui trie un nombre fixe de valeurs en utilisant une suite fixe de comparateurs. On peut voir un réseau de tri comme un réseau composé de fils et de comparateurs. Les valeurs, prises dans un ensemble ordonné, circulent le long des fils. Chaque comparateur connecte deux fils, compare les données qui entrent par les fils et les trie, sortant la plus petite donnée sur l'un des fils, la plus grande sur l’autre.

Tri par insertion

En informatique, le tri par insertion est un algorithme de tri classique. La plupart des personnes l'utilisent naturellement pour trier des cartes à jouer. En général, le tri par insertion est beaucoup plus lent que d'autres algorithmes comme le tri rapide (ou quicksort) et le tri fusion pour traiter de grandes séquences, car sa complexité asymptotique est quadratique. Le tri par insertion est cependant considéré comme l'algorithme le plus efficace sur des entrées de petite taille.

Tri à bulles

vignette|Visualisation statique du tri : les étapes vont de gauche à droite. À chaque étape une permutation est faite. La couleur la plus foncée a le plus de valeur et trouve sa place définitive (en bas) en premier. Le tri à bulles ou tri par propagation est un algorithme de tri. Il consiste à comparer répétitivement les éléments consécutifs d'un tableau, et à les permuter lorsqu'ils sont mal triés. Il doit son nom au fait qu'il déplace rapidement les plus grands éléments en fin de tableau, comme des bulles d'air qui remonteraient rapidement à la surface d'un liquide.

Algorithme de tri externe

Un algorithme de tri est dit externe lorsqu'il permet de trier des entrées trop grandes pour être contenues en intégralité dans la mémoire principale d'un ordinateur. En règle générale, la mémoire principale est la mémoire vive, et l'algorithme recourt donc à l'usage d'une mémoire située plus bas dans la hiérarchie mémoire, comme un disque dur. Recourir à la mémoire externe permet d'arriver à trier des volumes de données plus importants mais induit de nouvelles difficultés, le temps d'accès aux données étant beaucoup plus long.

Afficher plus

Séances de cours associées (26)

Fusionner Trier: Tri Algorithme

Explique l'algorithme de tri de fusion, son exactitude et sa complexité temporelle par rapport à d'autres algorithmes de tri.

Algorithmes de tri : sélection et insertion

Introduit des algorithmes de tri de sélection et d'insertion, expliquant leur exactitude et leur complexité temporelle.

Complexité et induction: Algorithmes et preuves

Couvre la complexité, les algorithmes et les preuves du pire cas, y compris l'induction mathématique et la récursion.

Algorithmes d'optimisation : approche de l'avidité

Explore les problèmes d'optimisation et les algorithmes gourmands pour une prise de décision efficace.

Multiplication matricielle et techniques de division et de conquête

Discute de la multiplication matricielle en utilisant des techniques de division et de conquête et introduit l'algorithme de Strassen pour une efficacité améliorée.

Afficher plus

Concepts associés (32)

Algorithme de tri externe

Afficher plus