Concept
In-place algorithm
Concepts associés (11)
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.
Tas binaire
En informatique, un tas binaire est une structure de données utilisée notamment pour implémenter une car elle permet de retirer l’élément de priorité maximale (resp. minimale) d'un ensemble ou d’insérer un élément dans l'ensemble en temps logarithmique tout en conservant la structure du tas binaire. On peut la représenter par un arbre binaire qui vérifie ces deux contraintes : C'est un arbre binaire complet : tous les niveaux sauf le dernier doivent être totalement remplis et si le dernier ne l'est pas totalement, alors il doit être rempli de gauche à droite.
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 de Shell
vignette|Tri de Shell barres de couleur de l'algorithme Le tri de Shell ou Shell sort en anglais est un algorithme de tri. C'est une amélioration notable du tri par insertion au niveau de la vitesse d'exécution, mais ce tri n'est pas stable. Le principe de l'algorithme est simple mais l'étude du temps d'exécution est très complexe, et plusieurs problèmes sont toujours ouverts à ce sujet. Le nom vient de son inventeur (1924-2015) qui publia l'algorithme dans le numéro de de Communications of the ACM.
Algorithme de sélection
En algorithmique, un algorithme de sélection est une méthode ayant pour but de trouver le k-ième plus petit élément d'un ensemble d'objets (étant donné un ordre et un entier k). La question de la sélection est un problème essentiel en algorithmique, notamment dans la recherche du maximum, du minimum et de la médiane. Plusieurs algorithmes ont été proposés et plusieurs contextes ont été étudiés : algorithmes en ligne, complexité amortie, complexité en moyenne, ensemble d'objet particuliers etc.
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 tas
thumb|300px|Animation montrant le fonctionnement du tri par tas (Heapsort). En informatique, le tri par tas est un algorithme de tri par comparaisons. Cet algorithme est de complexité asymptotiquement optimale, c'est-à-dire que l'on démontre qu'aucun algorithme de tri par comparaison ne peut avoir de complexité asymptotiquement meilleure. Sa complexité est proportionnelle à où est la longueur du tableau à trier.
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 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 fusion
En informatique, le tri fusion, ou tri dichotomique, est un algorithme de tri par comparaison stable. Sa complexité temporelle pour une entrée de taille n est de l'ordre de n log n, ce qui est asymptotiquement optimal. Ce tri est basé sur la technique algorithmique diviser pour régner. L'opération principale de l'algorithme est la fusion, qui consiste à réunir deux listes triées en une seule. L'efficacité de l'algorithme vient du fait que deux listes triées peuvent être fusionnées en temps linéaire.