Algorithme de triUn 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 fusionEn 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.
Arbre binaire de rechercheEn informatique, un arbre binaire de recherche ou ABR (en anglais, binary search tree ou BST) est une structure de données représentant un ensemble ou un tableau associatif dont les clés appartiennent à un ensemble totalement ordonné. Un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé.
Tri à bullesvignette|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.
SortingSorting 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 insertionEn 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électionLe 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 paquetsLe 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.
Logarithmevignette|Tracés des fonctions logarithmes en base 2, e et 10. En mathématiques, le logarithme (de logos : rapport et arithmos : nombre) de base d'un nombre réel strictement positif est la puissance à laquelle il faut élever la base pour obtenir ce nombre. Dans le cas le plus simple, le logarithme compte le nombre d'occurrences du même facteur dans une multiplication répétée : comme 1000 = 10×10×10 = 10, le logarithme en base 10 de 1000 est 3. Le logarithme de en base est noté : . John Napier a développé les logarithmes au début du .
Algorithme récursifUn algorithme récursif est un algorithme qui résout un problème en calculant des solutions d'instances plus petites du même problème. L'approche récursive est un des concepts de base en informatique. Les premiers langages de programmation qui ont autorisé l'emploi de la récursivité sont LISP et Algol 60. Depuis, tous les langages de programmation généraux réalisent une implémentation de la récursivité. Pour répéter des opérations, typiquement, un algorithme récursif s'appelle lui-même.
Recherche dichotomiqueLa recherche dichotomique, ou recherche par dichotomie (), est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié. Le principe est le suivant : comparer l'élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du tableau pertinente. Le nombre d'itérations de la procédure, c'est-à-dire le nombre de comparaisons, est logarithmique en la taille du tableau.
Self-balancing binary search treeIn computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that these abstract data structures receive the attribute "self-balancing".
Arbre binaireEn informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d'une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus deux éléments fils au niveau inférieur, habituellement appelés gauche et droit. Du point de vue de ces éléments fils, l'élément dont ils sont issus au niveau supérieur est appelé père. Au niveau le plus élevé, niveau 0, il y a un nœud racine.
FactorielleEn mathématiques, la factorielle d'un entier naturel n est le produit des nombres entiers strictement positifs inférieurs ou égaux à n. Cette opération est notée avec un point d'exclamation, n!, ce qui se lit soit « factorielle de n », soit « factorielle n », soit « n factorielle ». Cette notation a été introduite en 1808 par Christian Kramp. Par exemple, la factorielle 10 exprime le nombre de combinaisons possibles de placement des 10 convives autour d'une table (on dit la permutation des convives).
Logarithme naturelLe logarithme naturel ou logarithme népérien, ou encore logarithme hyperbolique jusqu'au , transforme, comme les autres fonctions logarithmes, les produits en sommes. L'utilisation de telles fonctions permet de faciliter les calculs comprenant de nombreuses multiplications, divisions et élévations à des puissances rationnelles. Il est souvent noté ln(). Le logarithme naturel ou népérien est dit de base e car ln(e) = 1. Le logarithme népérien d'un nombre x peut également être défini comme la puissance à laquelle il faut élever e pour obtenir x.
Comparison sortA comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator forms a total preorder over the data, with: if a ≤ b and b ≤ c then a ≤ c (transitivity) for all a and b, a ≤ b or b ≤ a (connexity). It is possible that both a ≤ b and b ≤ a; in this case either may come first in the sorted list.
Suite de Fibonaccivignette|Une juxtaposition de carrés dont les côtés ont pour longueur des nombres successifs de la suite de Fibonacci : 1, 1, 2, 3, 5, 8, 13 et 21. En mathématiques, la suite de Fibonacci est une suite d'entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent. Notée , elle est définie par , et pour . Les termes de cette suite sont appelés nombres de Fibonacci et forment la : vignette|Représentation géométrique de la fraction continue de φ faisant apparaître les nombres de la suite de Fibonacci.
Logarithme complexeEn mathématiques, le logarithme complexe est une fonction généralisant la fonction logarithme naturel (définie sur ]0,+∞[) au domaine C* des nombres complexes non nuls. Plusieurs définitions sont possibles. Aucune ne permet de conserver, à la fois, l'univocité, la continuité et les propriétés algébriques de la fonction logarithme. Histoire des nombres complexes La question de savoir s'il est possible de prolonger le logarithme naturel (c'est-à-dire de le définir sur un ensemble plus grand que ]0,+∞[) s'est posée dès la seconde moitié du avec les développements en série des fonctions.
Diviser pour régner (informatique)thumb|652x652px|Trois étapes (diviser, régner, combiner) illustrées avec l'algorithme du tri fusion En informatique, diviser pour régner (du latin , divide and conquer en anglais) est une technique algorithmique consistant à : Diviser : découper un problème initial en sous-problèmes ; Régner : résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits) ; Combiner : calculer une solution au problème initial à partir des solutions des sous-problèmes.
Algorithme de RémyL'algorithme de Rémy est un générateur d'arbres binaires, dont la principale application est un algorithme efficace de génération aléatoire d'arbres binaires. L'algorithme doit son nom à son inventeur Jean-Luc Rémy. L'algorithme de Rémy est dû à Jean-Luc Rémy, chercheur au Centre de recherche en informatique de Nancy. Il a été créé en 1978 sans être publié immédiatement et a fait partie du folklore de l'algorithmique et de la combinatoire énumérative jusqu'à sa parution dans une revue francophone en 1985.
