Séance de cours

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

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 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 (60)

Algorithmes en informatique: techniques de recherche et de tri

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

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.

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 d'optimisation : approche de l'avidité

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

Fusionner Trier: Diviser et conquérir

Explore l'algorithme Merge Sort, en appliquant efficacement l'approche Divide and Conquer au tri des tableaux.

Afficher plus

Concepts associés (13)