Séance de cours

Algorithmes de tri : sélection et insertion

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours couvre les bases des algorithmes de tri, en se concentrant sur le tri de sélection et le tri d'insertion. L'instructeur explique comment ces algorithmes fonctionnent, leur exactitude et leur complexité temporelle. La séance de cours présente également le paradigme «diviser pour mieux régner» et l'algorithme de tri de fusion récursif.

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.

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.

Tri rapide

En informatique, le tri rapide ou tri pivot (en anglais quicksort) est un algorithme de tri inventé par C.A.R. Hoare en 1961 et fondé sur la méthode de conception diviser pour régner. Il est généralement utilisé sur des tableaux, mais peut aussi être adapté aux listes. Dans le cas des tableaux, c'est un tri en place mais non stable. La complexité moyenne du tri rapide pour n éléments est proportionnelle à n log n, ce qui est optimal pour un tri par comparaison, mais la complexité dans le pire des cas est quadratique.

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 par sélection

Le tri par sélection (ou tri par extraction) est un algorithme de tri par comparaison. Cet algorithme est simple, mais considéré comme inefficace car il s'exécute en temps quadratique en le nombre d'éléments à trier, et non en temps pseudo linéaire. Sur un tableau de n éléments (numérotés de 0 à n-1 , attention un tableau de 5 valeurs (5 cases) sera numéroté de 0 à 4 et non de 1 à 5), le principe du tri par sélection est le suivant : rechercher le plus petit élément du tableau, et l'échanger avec l'élément d'indice 0 ; rechercher le second plus petit élément du tableau, et l'échanger avec l'élément d'indice 1 ; continuer de cette façon jusqu'à ce que le tableau soit entièrement trié.

Afficher plus

Séances de cours associées (64)

Fusionner Trier: Tri Algorithme

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

Dérivés, O-Notation

Explore les dérivés, la notation O, les extrema et la complexité des algorithmes dans Analysis 1.

Algorithmes en informatique: techniques de recherche et de tri

Fournit un aperçu des algorithmes de recherche et de tri essentiels en informatique.

Sélection Trier : Efficacité et Complexité

Explore l'efficacité et la complexité de l'algorithme de tri de sélection par rapport aux autres méthodes de tri.

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.

Afficher plus

Concepts associés (32)