Structure des données - Techniques de tri
Le tri fait référence à l'organisation des données dans un format particulier. L'algorithme de tri spécifie la manière d'organiser les données dans un ordre particulier. Les ordres les plus courants sont dans l'ordre numérique ou lexicographique.
L'importance du tri réside dans le fait que la recherche de données peut être optimisée à un niveau très élevé, si les données sont stockées de manière triée. Le tri est également utilisé pour représenter les données dans des formats plus lisibles. Voici quelques exemples de tri dans des scénarios réels -
Telephone Directory - L'annuaire téléphonique stocke les numéros de téléphone des personnes triés par leurs noms, afin que les noms puissent être recherchés facilement.
Dictionary - Le dictionnaire stocke les mots par ordre alphabétique afin que la recherche de n'importe quel mot devienne facile.
Tri sur place et tri sur place
Les algorithmes de tri peuvent nécessiter un espace supplémentaire pour la comparaison et le stockage temporaire de quelques éléments de données. Ces algorithmes ne nécessitent aucun espace supplémentaire et le tri est censé se produire sur place, ou par exemple, dans le tableau lui-même. C'est appeléin-place sorting. Le tri à bulles est un exemple de tri sur place.
Cependant, dans certains algorithmes de tri, le programme nécessite un espace supérieur ou égal aux éléments à trier. Le tri qui utilise un espace égal ou supérieur est appelénot-in-place sorting. Le tri par fusion est un exemple de tri non en place.
Tri stable et non stable
Si un algorithme de tri, après avoir trié les contenus, ne modifie pas la séquence de contenus similaires dans lesquels ils apparaissent, il est appelé stable sorting.
Si un algorithme de tri, après avoir trié le contenu, modifie la séquence de contenu similaire dans laquelle ils apparaissent, il est appelé unstable sorting.
La stabilité d'un algorithme est importante lorsque l'on souhaite conserver la séquence des éléments d'origine, comme dans un tuple par exemple.
Algorithme de tri adaptatif et non adaptatif
Un algorithme de tri est dit adaptatif s'il tire parti d'éléments déjà «triés» dans la liste à trier. Autrement dit, tout en triant si la liste source a un élément déjà trié, les algorithmes adaptatifs en tiendront compte et essaieront de ne pas les réorganiser.
Un algorithme non adaptatif est un algorithme qui ne prend pas en compte les éléments déjà triés. Ils essaient de forcer chaque élément à être réordonné pour confirmer leur tri.
Termes importants
Certains termes sont généralement inventés lors de la discussion des techniques de tri, voici une brève introduction à eux -
Ordre croissant
On dit qu'une séquence de valeurs est dans increasing order, si l'élément successif est supérieur au précédent. Par exemple, 1, 3, 4, 6, 8, 9 sont dans l'ordre croissant, car chaque élément suivant est supérieur à l'élément précédent.
Ordre décroissant
On dit qu'une séquence de valeurs est dans decreasing order, si l'élément successif est inférieur à l'élément courant. Par exemple, 9, 8, 6, 4, 3, 1 sont dans l'ordre décroissant, car chaque élément suivant est inférieur à l'élément précédent.
Ordre non croissant
On dit qu'une séquence de valeurs est dans non-increasing order, si l'élément successif est inférieur ou égal à son élément précédent dans la séquence. Cet ordre se produit lorsque la séquence contient des valeurs en double. Par exemple, 9, 8, 6, 3, 3, 1 sont dans un ordre non croissant, car chaque élément suivant est inférieur ou égal à (dans le cas de 3) mais pas supérieur à tout élément précédent.
Ordre non décroissant
On dit qu'une séquence de valeurs est dans non-decreasing order, si l'élément successif est supérieur ou égal à son élément précédent dans la séquence. Cet ordre se produit lorsque la séquence contient des valeurs en double. Par exemple, 1, 3, 3, 6, 8, 9 sont dans un ordre non décroissant, car chaque élément suivant est supérieur ou égal (dans le cas de 3) mais pas inférieur au précédent.