Algorithme de sélection

L'algorithme de base pour sélectionner la

• Trier la collection
• Si le résultat de l' algorithme de tri est un tableau , récupérez son

Le temps d'exécution de cette méthode est principalement dû à l'étape de tri, qui nécessite un temps d'exécution important avec un tri par comparaisonde tri d'entiers peuvent être utilisés, ils sont généralement plus lents que le temps linéaire pouvant être atteint avec des algorithmes de sélection spécialisés. Néanmoins, la simplicité de cette approche la rend attrayante, notamment lorsqu'une routine de tri hautement optimisée est fournie par la bibliothèque d'exécution, contrairement à l'algorithme de sélection. Pour des entrées de taille modérée, le tri peut être plus rapide que les algorithmes de sélection non aléatoires, en raison des facteurs constants plus faibles dans son

Pour un algorithme de tri qui génère un élément à la fois, comme le tri par sélection , le parcours peut être effectué simultanément au tri, et ce dernier peut être interrompu une fois le tournoi à élimination directe , où les équipes perdantes s'affrontent lors d'un mini-tournoi pour déterminer la deuxième place, illustre cette tri par tas donne l' algorithme de sélection par tas , capable de sélectionner la

De nombreuses méthodes de sélection reposent sur le choix d'un élément « pivot » spécifique dans l'ensemble d'entrée, puis sur la comparaison avec cet élément pour diviser les valeurs restantes en deux sous-ensembles : l'ensemble des éléments inférieurs au pivot et l'ensemble des éléments supérieurs au pivot. L'algorithme peut alors déterminer la

Comme pour l'algorithme de tri rapide par pivot , la partition de l'entrée en ensembles peut être réalisée en créant de nouvelles collections pour ces ensembles, ou par une méthode partitionnant directement une liste ou un tableau. Les détails varient selon la

• Si le pivot était exactement à la médiane de l'entrée, chaque appel récursif renverrait au maximum deux fois moins de valeurs que l'appel précédent, et le nombre total d'itérations augmenterait de géométrique
• Quickselect choisit le pivot de manière aléatoire et uniforme parmi les valeurs d'entrée. Il peut être décrit comme un algorithme d'élagage et de recherche , une variante de quicksort , avec la même stratégie de pivotement, mais là où quicksort effectue deux appels récursifs pour trier les deux sous-collections temps d'exécution moyen
• L' algorithme de Floyd-Rivest , une variante de quickselect, choisit un pivot en échantillonnant aléatoirement un sous-ensemble de valeurs de données, pour une générateur de nombres véritablement aléatoires , il a été prouvé qu'une version de l'algorithme de Floyd-Rivest utilisant un générateur de nombres pseudo-aléatoires initialisé avec seulement un nombre logarithmique de bits véritablement aléatoires s'exécute en temps linéaire avec une probabilité élevée.

• La méthode de la médiane des médianes partitionne l'entrée en ensembles de cinq éléments et utilise une autre méthode non récursive pour trouver la médiane de chacun de ces ensembles en temps constant par ensemble. Elle s'appelle ensuite récursivement pour trouver la médiane de ces médianes. L'utilisation de la médiane des médianes ainsi obtenue comme pivot produit une partition avec diviser pour régner qui ne se divise pas en deux
• Des algorithmes hybrides tels que introselect peuvent être utilisés pour atteindre les performances pratiques de quickselect avec un repli sur les médianes des médianes garantissant

Les algorithmes de sélection déterministes nécessitant le plus petit nombre de comparaisons connu, pour des valeurs très éloignées de Arnold Schönhage , Mike Paterson et Nick Pippenger des ordres partiels de certains types spécifiés, sur de petits sous-ensembles de valeurs d'entrée, en combinant des ordres partiels plus petits par comparaison. À titre d'exemple très simple, une fabrique peut prendre en entrée une séquence d'ordres partiels à un seul élément, comparer les éléments de ces ordres par paires et produire en sortie une séquence d'ensembles totalement ordonnés à deux éléments. Les éléments utilisés comme entrées de cette fabrique peuvent être soit des valeurs d'entrée n'ayant encore été comparées, soit des valeurs « inutilisées » produites par d'autres fabriques. L'objectif d'un algorithme de type « usine » est de combiner différentes usines, les sorties de certaines usines alimentant les entrées d'autres, afin d'obtenir un ordre partiel dans lequel un élément (le

Les algorithmes parallèles de sélection sont étudiés depuis 1975, date à laquelle Leslie Valiant a introduit le modèle d'arbre de comparaison parallèle pour analyser ces algorithmes. Il a démontré que, dans ce modèle, la sélection par un nombre linéaire de comparaisons nécessite des étapes parallèles, même pour sélectionner le minimum ou de RAM parallèle plus réaliste , utilisant un accès mémoire exclusif en lecture et en écriture, la sélection peut être effectuée en un temps O(n) processeurs , ce qui est optimal à la fois en termes de temps et de nombre de

Lorsque les données sont déjà organisées dans une structure de données , il est possible d'effectuer une sélection en un temps sous-linéaire par rapport au nombre de valeurs. À titre d'exemple simple, pour des données déjà triées dans un tableau, la sélection du

La sélection de données dans un tas binaire prend Ce temps est indépendant de la taille du tas et plus rapide que la limite de temps obtenue par la recherche du meilleur d'abordoptimisation combinatoire , comme la recherche des plus courts chemins dans un graphe pondéré, en définissant un espace d'états des solutions sous la forme d'un arbre ordonné de type tas implicite , puis en appliquant cet algorithme de sélection à cet de type file de priorité associée au tas, améliorant le temps d'extraction du i logarithme itéré

Pour un ensemble de données subissant des insertions et des suppressions dynamiques, l' arbre de statistiques d'ordre enrichit une structure d'arbre binaire de recherche auto-équilibrée d'une quantité constante d'informations supplémentaires par nœud, permettant ainsi d'effectuer les insertions, les suppressions et les requêtes de sélection demandant le Un algorithme de flux avec une complexité mémoire sous-linéaire en n et n ne peut pas résoudre exactement les requêtes de sélection pour des données dynamiques, mais l' algorithme de comptage-minimum permet de les résoudre approximativement, en trouvant une valeur dont la position dans l'ordre des éléments (si elle y était ajoutée) serait à un pas près de n , pour un algorithme dont la taille est à un facteur logarithmique près de n .