Tri fusion En informatique , un algorithme de tri est un algorithme qui ordonne les éléments d'une liste . Les ordres les plus fréquemment utilisés sont l'ordre numérique et l'o...
En informatique , un algorithme de tri est un algorithme qui ordonne les éléments d'une liste . Les ordres les plus fréquemment utilisés sont l'ordre numérique et l'ordre lexicographique , et soit l'ordre croissant, soit l'ordre décroissant. Un tri efficace est essentiel pour optimiser les performances d'autres algorithmes (tels que les algorithmes de recherche et de fusion ) qui nécessitent des données d'entrée triées. Le tri est également souvent utile pour normaliser les données et produire des résultats lisibles par l'humain.
Formellement, le résultat de tout algorithme de tri doit satisfaire deux conditions :
La sortie est dans un ordre monotone (chaque élément n'est ni plus petit ni plus grand que l'élément précédent, conformément à l'ordre requis).
Le résultat est une permutation (un réarrangement, tout en conservant tous les éléments originaux) de l'entrée.
Betty Holberton , qui travailla sur ENIAC et UNIVAC . Le tri à bulles fut analysé dès 1956. Les algorithmes asymptotiquement optimaux sont connus depuis le milieu du XXe siècle ; de nouveaux algorithmes sont encore développés régulièrement, comme Timsort, largement utilisé, datant de 2002, et l' algorithme de tri de bibliothèque, publié pour la première fois en 2006.
Les algorithmes de tri par comparaison reposent fondamentalement sur la réalisation de comparaisons. Les algorithmes qui ne reposent pas sur des comparaisons, comme le tri par dénombrement , peuvent offrir de meilleures performances.
Le tri optimal (avec le moins de comparaisons et d'échanges) ou rapide (en tenant compte des spécificités de la machine) des petits tableaux reste un problème de recherche ouvert, les solutions n'étant connues que pour les très petits tableaux (moins de 20 éléments). De même, le tri optimal (selon diverses définitions) sur une machine parallèle est un sujet de recherche ouvert.
Classification
Les algorithmes de tri peuvent être classés selon :
Comportement optimal, médiocre et moyen en fonction de la taille de la liste. Pour les algorithmes de tri séquentiel classiques, le bon comportement est en O( n log n ), le tri parallèle en O(log₂ n ) , et le mauvais comportement en O( n² ). Le comportement idéal pour un tri séquentiel est en O( n ), mais n'est pas possible en moyenne. Le tri parallèle optimal est en O(log n ) .
Récursivité : Certains algorithmes sont soit typiquement récursifs, soit typiquement non récursifs, tandis que d'autres peuvent être typiquement les deux (par exemple, le tri fusion).
Stabilité : les algorithmes de tri stables maintiennent l'ordre relatif des enregistrements ayant des clés (c'est-à-dire des valeurs) égales.
Qu'il s'agisse ou non d'un tri par comparaison . Un tri par comparaison examine les données uniquement en comparant deux éléments à l'aide d'un opérateur de comparaison.
Méthode générale : insertion, échange, sélection, fusion, etc. Les tris par échange comprennent le tri à bulles et le tri rapide. Les tris par sélection comprennent le tri cyclique et le tri par tas.
Que l'algorithme soit séquentiel ou parallèle, la suite de cette discussion se concentre presque exclusivement sur les algorithmes séquentiels et suppose un fonctionnement séquentiel.
Adaptabilité : L’influence du tri préalable des données d’entrée sur le temps d’exécution. Les algorithmes qui en tiennent compte sont dits adaptatifs .
En ligne : Un algorithme tel que le tri par insertion, fonctionnant en ligne, peut trier un flux constant d’entrées.
Stabilité
Exemple de tri stable sur des cartes à jouer. Lors d'un tri stable, les deux 5 conservent leur position initiale dans le résultat. En revanche, avec un tri instable, leur ordre peut être inversé.
Les algorithmes de tri stables trient les éléments égaux dans le même ordre que celui de leur apparition dans la liste d'entrée. Par exemple, dans l'exemple de tri de cartes à droite, les cartes sont triées par valeur, sans tenir compte de leur couleur. Ceci permet l'existence de plusieurs versions correctement triées de la liste originale. Les algorithmes de tri stables en choisissent une selon la règle suivante : si deux éléments sont égaux (comme les deux cartes de 5), leur ordre relatif est conservé ; autrement dit, si l'un précède l'autre dans la liste d'entrée, il le précédera dans la liste de sortie.
La stabilité est essentielle pour préserver l'ordre des données lors de plusieurs tris effectués sur un même ensemble de données . Par exemple, supposons que les fiches d'étudiants, composées du nom et de la section de cours, soient triées dynamiquement, d'abord par nom, puis par section de cours. Si un algorithme de tri stable est utilisé dans les deux cas, le tri par section de cours ne modifiera pas l'ordre des noms. En revanche, avec un tri instable, le tri par section pourrait mélanger l'ordre des noms, aboutissant à une liste d'étudiants non alphabétique.
Plus formellement, les données à trier peuvent être représentées par un enregistrement ou un tuple de valeurs, et la partie des données utilisée pour le tri est appelée la clé . Dans l'exemple des cartes, les cartes sont représentées par un enregistrement (valeur, couleur), et la clé est la valeur. Un algorithme de tri est stable si, pour deux enregistrements R et S ayant la même clé, et si R apparaît avant S dans la liste initiale, alors R apparaîtra toujours avant S dans la liste triée.
Lorsque des éléments égaux sont indiscernables, comme c'est le cas pour les entiers, ou plus généralement pour toute donnée où l'élément entier constitue la clé, la stabilité n'est pas un problème. La stabilité n'est pas non plus un problème si toutes les clés sont différentes.
Il est possible d'implémenter des algorithmes de tri instables pour les rendre stables. Une méthode consiste à étendre artificiellement la comparaison des clés afin que, en cas d'égalité entre deux objets ayant des clés identiques, l'ordre des éléments dans la liste d'entrée initiale serve de critère de départage. Cependant, la mémorisation de cet ordre peut engendrer des besoins supplémentaires en temps et en espace mémoire.
Une application des algorithmes de tri stable consiste à trier une liste à l'aide d'une clé primaire et d'une clé secondaire. Par exemple, supposons que nous souhaitions trier une main de cartes de sorte que les couleurs soient dans l'ordre suivant : trèfle (♣), carreau ( ♦ ), cœur ( ♥ ), pique (♠), et qu'au sein de chaque couleur, les cartes soient triées par valeur. On peut y parvenir en triant d'abord les cartes par valeur (à l'aide de n'importe quel algorithme de tri), puis en effectuant un tri stable par couleur.
Au sein de chaque couleur, le tri stable préserve le classement par rang déjà établi. Ce principe peut être étendu à un nombre quelconque de clés et est utilisé par le tri par base . On peut obtenir le même résultat avec un tri instable en utilisant une comparaison lexicographique des clés, qui, par exemple, compare d'abord par couleur, puis par rang si les couleurs sont identiques.
Comparaison des algorithmes
Cette analyse suppose que la longueur de chaque clé est constante et que toutes les comparaisons, les échanges et autres opérations peuvent s'effectuer en temps constant.
Légende:
complexité temporelle est indiquée pour chaque cas.
« Mémoire » désigne la quantité de stockage supplémentaire requise par l'algorithme.
Les temps d'exécution et les besoins en mémoire indiqués sont exprimés en notation grand O , par conséquent la base des logarithmes n'a pas d'importance.
La notation tris par comparaison . L'analyse mathématique démontre qu'un tri par comparaison ne peut pas être plus performant que
Les complexités ci-dessous supposent de machine à accès aléatoire à coût unitaire , les algorithmes dont le temps d'exécution est de , tels que le tri par base, prennent toujours un temps proportionnel à
Samplesort peut être utilisé pour paralléliser n'importe quel tri non comparatif, en distribuant efficacement les données dans plusieurs compartiments, puis en transmettant le tri à plusieurs processeurs, sans qu'il soit nécessaire de fusionner puisque les compartiments sont déjà triés entre eux.
Autres
Certains algorithmes sont lents comparés à ceux mentionnés précédemment, comme le tri bogosort, dont la complexité temporelle est illimitée, et le tri stooge, dont la complexité temporelle est en O ( n² ,⁷ ). Ces tris sont généralement présentés à des fins pédagogiques pour illustrer l'estimation de la complexité temporelle des algorithmes. Le tableau suivant décrit quelques algorithmes de tri impraticables pour une utilisation concrète dans les contextes logiciels traditionnels, en raison de leurs performances extrêmement faibles ou de leurs exigences matérielles spécifiques.
Les informaticiens théoriciens ont inventé d'autres algorithmes de tri qui offrent une complexité temporelle meilleure que O ( n log n ) sous certaines contraintes, notamment :
L'algorithme de Thorup, un algorithme de tri d'entiers randomisé , prenant un temps de tri d'entiers qui s'exécute en temps déterministe, et possède également une version aléatoire qui s'exécute en temps linéaire lorsque les mots sont suffisamment grands, en particulier (où w est la taille du mot).
Un algorithme de tri d'entiers randomisé prenant un temps moyen et un espace O ( n ).
algorithmes de tri populaires
Bien qu'il existe de nombreux algorithmes de tri, quelques-uns prédominent dans la pratique. Le tri par insertion est largement utilisé pour les petits ensembles de données, tandis que pour les grands ensembles, on privilégie un tri asymptotiquement efficace, principalement le tri par tas, le tri fusion ou le tri rapide. Les implémentations efficaces utilisent généralement un algorithme hybride , combinant un algorithme asymptotiquement efficace pour le tri global avec le tri par insertion pour les petites listes en fin de boucle récursive. Les implémentations hautement optimisées utilisent des variantes plus sophistiquées, telles que Timsort (tri fusion, tri par insertion et logique additionnelle), utilisé dans Android , Java et Python , et introsort (tri rapide et tri par tas), utilisé (sous différentes formes) dans certaines implémentations de tri en C++ et dans .NET .
Pour des données plus restreintes, comme des nombres dans un intervalle fixe, on utilise fréquemment des tris par distribution tels que le tri par dénombrement ou le tri par base. Le tri à bulles et ses variantes sont rarement utilisés en pratique, mais sont souvent rencontrés dans l'enseignement et les discussions théoriques.
Lorsqu'on trie physiquement des objets (comme classer des feuilles, des copies ou des livres par ordre alphabétique), on utilise intuitivement le tri par insertion pour les petits ensembles. Pour les plus grands, on commence souvent par un tri par compartiments, par exemple par initiale, et ce tri par compartiments multiples permet de trier efficacement de très grands ensembles. L'espace est souvent peu coûteux, par exemple en étalant les objets au sol ou sur une grande surface, mais les opérations sont coûteuses, surtout lorsqu'il s'agit de déplacer un objet sur une grande distance ; la localité de référence est donc importante. Le tri fusion est également pratique pour les objets physiques, notamment parce qu'on peut utiliser les deux mains, une pour chaque liste à fusionner, tandis que d'autres algorithmes, comme le tri par tas ou le tri rapide, sont mal adaptés à l'usage humain. D'autres algorithmes encore, comme le tri de bibliothèque , une variante du tri par insertion qui conserve des espaces, sont également pratiques pour une utilisation physique.
tri simple
Deux des tris les plus simples sont le tri par insertion et le tri par sélection. Tous deux sont efficaces sur de petits ensembles de données, grâce à leur faible surcharge, mais moins performants sur de grands ensembles. En pratique, le tri par insertion est généralement plus rapide que le tri par sélection, car il effectue moins de comparaisons et offre de bonnes performances sur des données presque triées. Il est donc privilégié. Cependant, le tri par sélection utilise moins d'écritures et est ainsi utilisé lorsque les performances d'écriture sont un facteur limitant.
Tri par insertion
Le tri par insertion est un algorithme de tri simple, relativement efficace pour les petites listes et les listes déjà triées. Il est souvent utilisé dans des algorithmes plus complexes. Son principe consiste à insérer les éléments un à un dans une nouvelle liste triée, à la manière d'ajouter de l'argent à son portefeuille. Dans les tableaux, la nouvelle liste et les éléments restants peuvent partager l'espace du tableau, mais l'insertion est coûteuse, car elle nécessite de décaler tous les éléments suivants d'une position. Le tri Shell est une variante du tri par insertion, plus efficace pour les grandes listes.
Tri par sélection
tri par comparaison en place . Sa complexité est de O ( n² ), ce qui le rend inefficace pour les grandes listes, et ses performances sont généralement inférieures à celles du tri par insertion . Le tri par sélection est apprécié pour sa simplicité et présente également des avantages en termes de performances par rapport à des algorithmes plus complexes dans certaines situations.
L'algorithme trouve la valeur minimale, l'échange avec la valeur en première position, et répète ces étapes pour le reste de la liste. Il n'effectue pas plus de n échanges et est donc utile lorsque les échanges sont très coûteux.
Tri efficace
Les algorithmes de tri général pratiques sont presque toujours basés sur un algorithme dont la complexité temporelle moyenne (et généralement la complexité dans le pire des cas) est O( n log n ). Parmi les plus courants, on trouve le tri par tas, le tri fusion et le tri rapide. Chacun présente des avantages et des inconvénients, les plus importants étant que l'implémentation simple du tri fusion utilise O( n ) espace supplémentaire, et que l'implémentation simple du tri rapide a une complexité dans le pire des cas de O( n² ) . Ces problèmes peuvent être résolus ou atténués au prix d'un algorithme plus complexe.
Bien que ces algorithmes soient asymptotiquement efficaces sur des données aléatoires, diverses modifications sont apportées pour une efficacité pratique sur des données réelles. Premièrement, la surcharge de ces algorithmes devient significative pour les petits volumes de données ; un algorithme hybride est donc souvent utilisé, généralement avec un passage au tri par insertion lorsque les données sont suffisamment petites. Deuxièmement, ces algorithmes sont souvent peu performants sur des données déjà triées ou presque triées – or, ces données sont fréquentes dans le monde réel et peuvent être triées en O( n ) par des algorithmes appropriés. Enfin, ils peuvent également être instables , et la stabilité est souvent une propriété souhaitable pour un algorithme de tri. C'est pourquoi des algorithmes plus sophistiqués sont souvent employés, tels que Timsort (basé sur le tri fusion) ou introsort (basé sur le tri rapide, avec recours au tri par tas en cas de besoin).
Tri fusion
les listes chaînées peuvent être triées par fusion avec un espace supplémentaire constant, ce qui en fait l'algorithme de choix pour le tri des listes chaînées.
Le tri fusion a connu un regain de popularité relativement récent pour les implémentations pratiques, grâce à son utilisation dans l'algorithme sophistiqué Timsort , qui constitue la routine de tri standard des langages de programmation Python et Java (depuis JDK 7 ). Le tri fusion est lui-même la routine standard en Perl [ , entre autres, et est utilisé en Java au moins depuis 2000 dans JDK 1.3
Tri en tas
tri par sélection . Il fonctionne également en déterminant le plus grand (ou le plus petit) élément de la liste, en le plaçant à la fin (ou au début) de la liste, puis en parcourant le reste de la liste. Cependant, il accomplit cette tâche efficacement grâce à une structure de données appelée tas , un type particulier d' arbre binaire . Une fois la liste de données transformée en tas, le nœud racine est garanti d'être le plus grand (ou le plus petit) élément. Lorsqu'il est retiré et placé à la fin de la liste, le tas est réorganisé de sorte que le plus grand élément restant devienne la racine. Grâce au tas, la recherche du prochain plus grand élément prend un temps O(log n ), au lieu de O( n ) pour un parcours linéaire comme dans le tri par sélection simple. Cela permet au tri par tas de s'exécuter en O( n log n ), ce qui représente également sa complexité dans le pire des cas.
Tri rapide
algorithme de type « diviser pour régner » qui repose sur une opération de partitionnement : pour partitionner un tableau, un élément appelé pivot est sélectionné. Tous les éléments inférieurs au pivot sont placés avant lui et tous les éléments supérieurs sont placés après. Cette opération peut être réalisée efficacement en temps linéaire et sur place . Les sous-listes « inférieur » et « supérieur » sont ensuite triées récursivement. On obtient ainsi une complexité temporelle moyenne de O( n log n ), avec un faible surcoût, ce qui explique la popularité de cet algorithme. Les implémentations efficaces du tri rapide (avec partitionnement sur place) sont généralement des tris instables et relativement complexes, mais figurent parmi les algorithmes de tri les plus rapides en pratique. Grâce à son utilisation modeste d'espace mémoire (O(log n) ), le tri rapide est l'un des algorithmes de tri les plus populaires et est disponible dans de nombreuses bibliothèques de programmation standard.
L'inconvénient majeur du tri rapide est que sa complexité dans le pire des cas est de O( n² ). Bien que rare, ce cas se produit fréquemment avec des données triées dans des implémentations naïves (choix du premier ou du dernier élément comme pivot), ce qui est courant. Le principal défi du tri rapide réside donc dans le choix d'un bon pivot, car des choix systématiquement mauvais peuvent entraîner une complexité drastique de O( n² ) , tandis qu'un bon choix permet d'atteindre une complexité de O( n log n ), asymptotiquement optimale. Par exemple, si la médiane est choisie comme pivot à chaque étape, l'algorithme s'exécute en O( n log n ). Cependant, la recherche de la médiane, par exemple par l' algorithme de sélection de la médiane des médianes , est une opération en O( n ) sur des listes non triées et induit donc un surcoût important lié au tri. En pratique, le choix d'un pivot aléatoire conduit presque systématiquement à une complexité de O( n log n ).
Si une garantie de performance en O( n log n ) est importante, une modification simple permet de l'obtenir. L'idée, due à Musser, consiste à limiter la profondeur maximale de récursion. Si cette limite est dépassée, le tri se poursuit à l'aide de l'algorithme de tri par tas. Musser a proposé que cette limite soit de l'ordre de 1/n , soit environ le double de la profondeur de récursion maximale attendue en moyenne avec un Le tri Shell, différent du tri à bulles en ce qu'il déplace les éléments vers de nombreuses positions d'échange, est un tri qui permet d'effectuer des échanges.Donald Shell en 1959 O( n² ) , où k représente la plus grande distance entre deux éléments mal placés. Cela signifie qu'en général, sa complexité est de O ( n² ), mais pour des données majoritairement triées, avec seulement quelques éléments mal placés, il est plus rapide. Ainsi, en triant d'abord les éléments les plus éloignés, puis en réduisant progressivement l'écart entre les éléments à trier, le tri final est beaucoup plus rapide. Une implémentation possible consiste à organiser la séquence de données dans un tableau bidimensionnel, puis à trier les colonnes de ce tableau à l'aide du tri par insertion.
La complexité temporelle dans le pire des cas de Shellsort est un problème ouvert et dépend de la séquence d'intervalles utilisée, les complexités connues allant de O ( n² ) à O ( n⁴ /³ ) et Θ( n log₂ n ) . Ce constat, combiné au fait que Shellsort s'exécute en place , ne nécessite qu'une quantité de code relativement faible et n'utilise pas la pile d'appels , le rend utile dans les situations où la mémoire est une ressource précieuse, comme dans les systèmes embarqués et les noyaux de systèmes d'exploitation .
Tri à bulles et variantes
Le tri à bulles, ainsi que ses variantes comme le tri en peigne et le tri cocktail , sont des algorithmes de tri simples mais très inefficaces. On les rencontre fréquemment dans les manuels d'introduction en raison de leur facilité d'analyse, mais ils sont rarement utilisés en pratique.
Tri à bulles
Le tri à bulles est un algorithme de tri qui parcourt continuellement une liste, en échangeant les éléments jusqu'à ce qu'ils apparaissent dans le bon ordre.du tri à bulles et conçu initialement par Włodzimierz Dobosiewicz en 1980 Il a ensuite été redécouvert et popularisé par Stephen Lacey et Richard Box dans un article de Byte Magazine paru en avril 1991. L'idée principale est d'éliminer les « tortues » , c'est-à-dire les petites valeurs en fin de liste, car elles ralentissent considérablement le tri à bulles. ( Les « lapins » , c'est-à-dire les grandes valeurs en début de liste, ne posent pas de problème dans le tri à bulles.) Pour ce faire, l'algorithme échange initialement les éléments situés à une certaine distance les uns des autres dans le tableau, au lieu de les échanger uniquement s'ils sont adjacents, puis réduit progressivement cette distance jusqu'à obtenir un fonctionnement similaire à celui d'un tri à bulles classique. Ainsi, si le tri Shell peut être vu comme une généralisation du tri par insertion qui échange les éléments espacés d'une certaine distance, le tri en peigne peut être vu comme la même généralisation appliquée au tri à bulles.
tris de distribution
tri par casiers et le tri flash sont des algorithmes de tri par distribution. Ces algorithmes peuvent être exécutés sur un seul processeur ou être distribués , auquel cas des sous-ensembles sont triés séparément sur différents processeurs, puis combinés. Ceci permet le tri externe de données trop volumineuses pour tenir dans la mémoire d'un seul ordinateur.
Tri par dénombrement
type « diviser pour régner » qui généralise le tri par dénombrement en partitionnant un tableau en un nombre fini de compartiments. Chaque compartiment est ensuite trié individuellement, soit à l'aide d'un algorithme de tri différent, soit en appliquant récursivement l'algorithme de tri par compartiments.
Le tri par compartiments fonctionne de manière optimale lorsque les éléments de l'ensemble de données sont répartis uniformément dans tous les compartiments.
Tri par base
chiffre le moins significatif (LSD), soit en commençant par le chiffre le plus significatif (MSD). L'algorithme LSD trie d'abord la liste par chiffre le moins significatif tout en préservant leur ordre relatif grâce à un tri stable. Il les trie ensuite par chiffre suivant, et ainsi de suite du moins significatif au plus significatif, pour obtenir une liste triée. Alors que le tri par base LSD requiert l'utilisation d'un tri stable, l'algorithme de tri par base MSD n'en a pas besoin (sauf si un tri stable est souhaité). Le tri par base MSD en place n'est pas stable. Il est courant que l' algorithme de tri par dénombrement soit utilisé en interne par le tri par base. Une approche de tri hybride , telle que l'utilisation du tri par insertion pour les petits intervalles, améliore considérablement les performances du tri par base.
Tableau des temps d'exécution des algorithmes populaires
Modèles d'utilisation de la mémoire et tri par index
Lorsque la taille du tableau à trier approche ou dépasse la mémoire vive disponible, nécessitant l'utilisation d'un disque ou d'un espace d'échange (beaucoup plus lent), le comportement de l'algorithme de tri en matière de mémoire devient crucial. Un algorithme relativement efficace lorsque le tableau tenait facilement en RAM peut alors devenir impraticable. Dans ce cas, le nombre total de comparaisons perd de son importance relative, et le nombre de copies ou d'échanges de portions de mémoire avec le disque peut devenir prépondérant dans les performances de l'algorithme. Ainsi, le nombre de passages et la localisation des comparaisons peuvent s'avérer plus importants que le nombre brut de comparaisons, car les comparaisons entre éléments voisins s'effectuent à la vitesse du bus système (voire, avec la mise en cache, à la vitesse du processeur ), ce qui, comparé à la vitesse du disque, est quasiment instantané.
Par exemple, l' algorithme de tri rapide récursif, très répandu , offre des performances tout à fait acceptables avec une quantité de RAM suffisante. Cependant, du fait de sa méthode récursive de copie de portions du tableau, il devient beaucoup moins pratique lorsque le tableau ne tient pas en RAM, car cela peut engendrer de nombreuses opérations de copie ou de déplacement lentes entre le disque et le système. Dans ce cas, un autre algorithme peut s'avérer préférable, même s'il nécessite un plus grand nombre de comparaisons.
Une solution à ce problème, efficace lors du tri d'enregistrements complexes (comme dans une base de données relationnelle ) selon un champ clé relativement petit, consiste à créer un index dans le tableau, puis à trier cet index plutôt que le tableau entier. (Une version triée du tableau entier peut alors être générée en une seule passe, en lisant l'index, mais souvent, cela est inutile, car disposer de l'index trié suffit.) L'index étant beaucoup plus petit que le tableau entier, il peut facilement être stocké en mémoire, contrairement au tableau entier, éliminant ainsi le problème des échanges disque. Cette procédure est parfois appelée « tri par étiquette ».
Une autre technique pour surmonter le problème de la taille de la mémoire consiste à utiliser un tri externe . Par exemple, une méthode possible est de combiner deux algorithmes en tirant parti des atouts de chacun pour améliorer les performances globales. Ainsi, le tableau peut être subdivisé en blocs dont la taille tient en RAM, le contenu de chaque bloc trié à l'aide d'un algorithme efficace (tel que le tri rapide ), et les résultats fusionnés par une fusion à k voies similaire à celle utilisée dans le tri fusion . Cette méthode est plus rapide que d'appliquer le tri fusion ou le tri rapide à la liste entière.
Il est également possible de combiner différentes techniques. Pour le tri de très grands ensembles de données dépassant largement la mémoire système, il peut même être nécessaire de trier l'index à l'aide d'un algorithme ou d'une combinaison d'algorithmes conçus pour fonctionner de manière optimale avec la mémoire virtuelle , c'est-à-dire pour réduire le nombre d'échanges de données requis.
Algorithmes associés
Les problèmes connexes incluent le tri approximatif (trier une séquence à une certaine précision de l'ordre correct), le tri partiel (trier uniquement les k plus petits éléments d'une liste, ou trouver les k plus petits éléments, mais non triés) et la sélection (calculer le k -ième plus petit élément). Ces problèmes peuvent être résolus de manière inefficace par un tri total, mais des algorithmes plus efficaces existent, souvent dérivés de la généralisation d'un algorithme de tri. L'exemple le plus notable est quickselect , qui est lié à quicksort . Inversement, certains algorithmes de tri peuvent être dérivés par application répétée d'un algorithme de sélection ; quicksort et quickselect peuvent être vus comme le même pivotement, différant seulement par le fait que l'un s'applique aux deux côtés (quicksort, diviser pour régner ) ou à un seul côté (quickselect, diminuer pour régner ).
Un algorithme de mélange est en quelque sorte l'inverse d'un algorithme de tri . Ils sont fondamentalement différents car ils nécessitent une source de nombres aléatoires. Le mélange peut également être implémenté par un algorithme de tri, plus précisément par un tri aléatoire : on attribue un nombre aléatoire à chaque élément de la liste, puis on trie en fonction de ces nombres aléatoires. Cependant, cette méthode est rarement utilisée en pratique, et il existe un algorithme de mélange simple et efficace bien connu : le mélange de Fisher-Yates .
Les algorithmes de tri sont inefficaces pour établir un ordre dans de nombreuses situations. Généralement, cela se produit lorsque les éléments ne disposent pas de fonction de comparaison fiable (préférences issues du crowdsourcing, comme dans les systèmes de vote ), lorsque les comparaisons sont très coûteuses ( sport ), ou encore lorsqu'il est impossible de comparer tous les éléments deux à deux pour tous les critères ( moteurs de recherche ). Dans ces cas, on parle généralement de classement, et l'objectif est de trouver le « meilleur » résultat pour certains critères, selon des probabilités déduites des comparaisons ou des classements. Un exemple courant est celui des échecs, où les joueurs sont classés selon le système de classement Elo , et où les classements sont déterminés par un système de tournois plutôt que par un algorithme de tri.
Il existe des algorithmes de tri pour un comparateur « bruité » (potentiellement incorrect) et des algorithmes de tri pour une paire de comparateurs « rapides et imparfaits » (c’est-à-dire « bruités ») et « propres ». Cela peut s’avérer utile lorsque la fonction de comparaison complète est coûteuse.
Worldlex Wiki 
