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.
Simple random sampleIn statistics, a simple random sample (or SRS) is a subset of individuals (a sample) chosen from a larger set (a population) in which a subset of individuals are chosen randomly, all with the same probability. It is a process of selecting a sample in a random way. In SRS, each subset of k individuals has the same probability of being chosen for the sample as any other subset of k individuals. A simple random sample is an unbiased sampling technique. Simple random sampling is a basic type of sampling and can be a component of other more complex sampling methods.
Échantillonnage stratifiévignette|Vous prenez un échantillon aléatoire stratifié en divisant d'abord la population en groupes homogènes (semblables en eux-mêmes) (strates) qui sont distincts les uns des autres, c'est-à-dire. Le groupe 1 est différent du groupe 2. Ensuite, choisissez un EAS (échantillon aléatoire simple) distinct dans chaque strate et combinez ces EAS pour former l'échantillon complet. L'échantillonnage aléatoire stratifié est utilisé pour produire des échantillons non biaisés.
Algorithme de tri externeUn algorithme de tri est dit externe lorsqu'il permet de trier des entrées trop grandes pour être contenues en intégralité dans la mémoire principale d'un ordinateur. En règle générale, la mémoire principale est la mémoire vive, et l'algorithme recourt donc à l'usage d'une mémoire située plus bas dans la hiérarchie mémoire, comme un disque dur. Recourir à la mémoire externe permet d'arriver à trier des volumes de données plus importants mais induit de nouvelles difficultés, le temps d'accès aux données étant beaucoup plus long.
Échantillonnage (statistiques)thumb|Exemple d'échantillonnage aléatoire En statistique, l'échantillonnage désigne les méthodes de sélection d'un sous-ensemble d'individus (un échantillon) à l'intérieur d'une population pour estimer les caractéristiques de l'ensemble de la population. Cette méthode présente plusieurs avantages : une étude restreinte sur une partie de la population, un moindre coût, une collecte des données plus rapide que si l'étude avait été réalisé sur l'ensemble de la population, la réalisation de contrôles destructifs Les résultats obtenus constituent un échantillon.
Cluster samplingIn statistics, cluster sampling is a sampling plan used when mutually homogeneous yet internally heterogeneous groupings are evident in a statistical population. It is often used in marketing research. In this sampling plan, the total population is divided into these groups (known as clusters) and a simple random sample of the groups is selected. The elements in each cluster are then sampled. If all elements in each sampled cluster are sampled, then this is referred to as a "one-stage" cluster sampling plan.
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 à 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.
Nonprobability samplingSampling is the use of a subset of the population to represent the whole population or to inform about (social) processes that are meaningful beyond the particular cases, individuals or sites studied. Probability sampling, or random sampling, is a sampling technique in which the probability of getting any particular sample may be calculated. In cases where external validity is not of critical importance to the study's goals or purpose, researchers might prefer to use nonprobability sampling.
Patience sortingIn computer science, patience sorting is a sorting algorithm inspired by, and named after, the card game patience. A variant of the algorithm efficiently computes the length of a longest increasing subsequence in a given array. The algorithm's name derives from a simplified variant of the patience card game. The game begins with a shuffled deck of cards. The cards are dealt one by one into a sequence of piles on the table, according to the following rules. Initially, there are no piles.
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.
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é.
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.
Survey samplingIn statistics, survey sampling describes the process of selecting a sample of elements from a target population to conduct a survey. The term "survey" may refer to many different types or techniques of observation. In survey sampling it most often involves a questionnaire used to measure the characteristics and/or attitudes of people. Different ways of contacting members of a sample once they have been selected is the subject of survey data collection.
Systematic samplingIn survey methodology, systematic sampling is a statistical method involving the selection of elements from an ordered sampling frame. The most common form of systematic sampling is an equiprobability method. In this approach, progression through the list is treated circularly, with a return to the top once the list ends. The sampling starts by selecting an element from the list at random and then every kth element in the frame is selected, where k, is the sampling interval (sometimes known as the skip): this is calculated as: where n is the sample size, and N is the population size.
Algorithme de sélectionEn 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.
Algorithmethumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le , le traitement de textes, la bio-informatique L' algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation.
Nondeterministic algorithmIn computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different runs due to a race condition. A probabilistic algorithm's behaviors depends on a random number generator.
Tri de nombres entiersEn informatique, le tri de nombres entiers est le problème algorithmique consistant à trier une collection d'éléments au moyen de clés numériques, chacune étant un nombre entier. Les algorithmes conçus pour le tri des nombres entiers peuvent également souvent être appliqués aux problèmes de tri dans lesquels les clés sont des nombres décimaux, des nombres rationnels ou des chaînes de texte.
