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

Tri de sélection: Mise en œuvre et exercice

Description

Cette séance de cours couvre la mise en œuvre de l'algorithme de tri de sélection, en commençant par créer une liste d'entiers aléatoires et trouver l'index de l'élément minimum. L'instructeur explique comment mettre en œuvre l'algorithme de tri de sélection et fournit une marche à suivre détaillée du processus, y compris l'échange d'éléments pour trier efficacement la liste.

Source officielle

Proximité ontologique

Informatique théorique

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

Concepts associés (13)

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.

Sorting

Sorting refers to ordering data in an increasing or decreasing manner according to some linear relationship among the data items. ordering: arranging items in a sequence ordered by some criterion; categorizing: grouping items with similar properties. Ordering items is the combination of categorizing them based on equivalent order, and ordering the categories themselves. In , arranging in an ordered sequence is called "sorting". Sorting is a common operation in many applications, and efficient algorithms have been developed to perform it.

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é.

Tri par paquets

Le tri par paquets est un algorithme de tri qui fonctionne sur des nombres réels appartenant à un intervalle borné fixé à l'avance. Le principe de ce tri consiste à partitionner régulièrement l'intervalle d'entrée en autant de sous-intervalles que l'entrée comporte d'éléments à trier, et à distribuer les données selon leur valeurs en autant de paquets correspondant à ces sous-intervalles. Les paquets sont alors triés séparément à l'aide d'un autre algorithme de tri.

Afficher plus

Séances de cours associées (36)

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.

Algorithmes de tri : Méthodes de tri et comparaison

Explore les méthodes de tri, le tri d'insertion et la comparaison d'algorithmes pour une organisation efficace des données.

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.

Tri récursif: Fusionner Trier

Explique le tri récursif en utilisant Merge Sort et sa complexité linearyithmique.

Algorithmes de tri récursif

Explore les algorithmes de tri récursif, la récursion, la programmation dynamique et l'efficacité des solutions récursives.

Afficher plus

Concepts associés (13)