Tri - Sorting
Le tri est tout processus d'organisation systématique des éléments et a deux significations communes, mais distinctes:
- ordonner : organiser les articles dans une séquence ordonnée par un certain critère;
- catégorisation : regrouper des éléments avec des propriétés similaires.
La commande des articles consiste à les classer en fonction d'un ordre équivalent et à classer les catégories elles-mêmes.
Tri des informations ou des données
En informatique , organiser dans une séquence ordonnée est appelé «tri». Le tri est une opération courante dans de nombreuses applications, et des algorithmes efficaces pour l'exécuter ont été développés.
Les utilisations les plus courantes des séquences triées sont:
- rendre la recherche ou la recherche efficace;
- rendre la fusion de séquences efficace.
- permettre le traitement des données dans un ordre défini.
L'opposé du tri, la réorganisation d'une séquence d'éléments dans un ordre aléatoire ou dénué de sens, est appelé mélange .
Pour le tri, soit un ordre faible, "ne doit pas venir après", peut être spécifié, soit un ordre faible strict , "doit venir avant" (en spécifiant que l'un définit aussi l'autre, les deux sont le complément de l'inverse de l'autre, voir opérations sur les relations binaires ). Pour que le tri soit unique, ces deux éléments sont limités respectivement à un ordre total et un ordre total strict.
Le tri des n-uplets (en fonction du contexte, également appelé, par exemple, des enregistrements constitués de champs) peut être effectué en fonction d'un ou plusieurs de ses composants. Plus généralement, les objets peuvent être triés en fonction d'une propriété. Un tel composant ou propriété est appelé une clé de tri .
Par exemple, les éléments sont des livres, la clé de tri est le titre, le sujet ou l'auteur et l'ordre est alphabétique.
Une nouvelle clé de tri peut être créée à partir de deux clés de tri ou plus par ordre lexicographique . La première est alors appelée clé de tri primaire , la seconde clé de tri secondaire , etc.
Par exemple, les adresses peuvent être triées en utilisant la ville comme clé de tri principale et la rue comme clé de tri secondaire.
Si les valeurs de la clé de tri sont totalement ordonnées , la clé de tri définit un ordre faible des éléments: les éléments avec la même clé de tri sont équivalents en ce qui concerne le tri. Voir aussi le tri stable . Si différents éléments ont des valeurs de clé de tri différentes, cela définit un ordre unique des éléments.
Un ordre standard est souvent appelé ascendant (correspondant au fait que l'ordre standard des nombres est croissant, c'est-à-dire A à Z, 0 à 9), l'ordre inverse décroissant (Z à A, 9 à 0). Pour les dates et les heures, croissant signifie que les valeurs antérieures précèdent les plus récentes, par exemple 1/1/2000 triera avant le 1/1/2001.
Algorithmes de tri courants
- Tri Bubble / Shell : échangez deux éléments adjacents s'ils sont dans le désordre. Répétez jusqu'à ce que le tableau soit trié.
- Tri par insertion : scannez les éléments successifs pour un article en panne, puis insérez l'article au bon endroit.
- Tri par sélection : trouvez le plus petit (ou le plus grand) élément du tableau et placez-le au bon endroit. Échangez-le avec la valeur en première position. Répétez jusqu'à ce que le tableau soit trié.
- Tri rapide : partitionnez le tableau en deux segments. Dans le premier segment, tous les éléments sont inférieurs ou égaux à la valeur du pivot. Dans le deuxième segment, tous les éléments sont supérieurs ou égaux à la valeur de pivot. Enfin, triez les deux segments de manière récursive.
- Tri par fusion : divisez la liste des éléments en deux parties, triez les deux parties individuellement, puis fusionnez-la.
Processus de tri physique
Différentes tâches de tri sont essentielles dans les processus industriels. Par exemple, lors de l'extraction de l' or à partir du minerai, un dispositif appelé table à secouer utilise la gravité , les vibrations et le débit pour séparer l' or des matériaux plus légers du minerai (tri par taille et poids). Le tri est également un processus naturel qui se traduit par une concentration de minerai ou de sédiments . Le tri résulte de l'application d'un critère ou de facteurs de stress différentiels à une masse pour la séparer en ses composants en fonction d'une qualité variable. Les matériaux qui sont différents, mais seulement légèrement, comme les isotopes de l'uranium, sont très difficiles à séparer.
Le tri optique est un processus automatisé de tri de produits solides à l'aide de caméras et / ou de lasers et est largement utilisé dans l'industrie alimentaire. Le tri par capteur est utilisé dans le traitement des minéraux.
Voir également
- Aide: tri dans les tableaux Wikipédia. Pour le tri des catégories, voir Wikipedia: Catégorisation # Clés de tri et pour le tri des sections d'article, voir WP: ORDER
- Collation
- Tri / fusion mainframe IBM
- Algorithme de classement Unicode
- Knolling
- 5S (méthodologie)
Les références
Liens externes
- Démonstration d'algorithmes de tri (comprend la bulle et le tri rapide)
- Vidéo animée expliquant le tri des bulles et le tri rapide et compare leurs performances.