Stabilité des algorithmes de tri - Un traitement de l'égalité

Les algorithmes sont au cœur de l'informatique. Les algorithmes utilisés pour le tri sont parmi les plus fondamentaux, utiles et, par conséquent, omniprésents.

Algorithme - un ensemble fini d'étapes non ambiguës pour résoudre un problème spécifique.

Nous trions et nous reposons constamment et souvent inconsciemment sur l'ordre des objets groupés. Par exemple, nous classons les tâches sur une liste en fonction de leur priorité. Nous empilons les livres sur des étagères en fonction de leur hauteur. Nous trions les lignes dans une feuille de calcul ou une base de données, ou nous nous basons sur l'ordre alphabétique des mots dans un dictionnaire. Parfois, on perçoit même une certaine beauté dans des arrangements ordonnés.

En tant que programmeurs, savoir comment nous trions est important car cela affecte à quoi pourrait ressembler un arrangement trié. Toutes les sortes n'ordonnent pas les objets de la même manière! Pour cette raison, les résultats des opérations de tri diffèrent en fonction des algorithmes utilisés. Si cela n'est pas reconnu, nous pourrions nous surprendre ou surprendre les utilisateurs de notre logiciel.

La stabilité des algorithmes de tri est l'une de leurs propriétés distinctives. Il traite de la façon dont l'algorithme traite les éléments comparables avec des clés de tri égales.

Clé de tri - Une clé utilisée pour déterminer l'ordre des éléments dans une collection, par exemple l'âge, la hauteur, la position dans l'alphabet, etc.

Un algorithme de tri stable maintient l'ordre relatif des éléments avec des clés de tri égales. Un algorithme de tri instable ne le fait pas. En d'autres termes, lorsqu'une collection est triée avec un algorithme de tri stable, les éléments avec les mêmes clés de tri conservent leur ordre une fois la collection triée.

Un exemple, un code et une démo

L'image ci-dessus illustre l'effet d'un tri stable. Sur la gauche, les données ont été triées par ordre alphabétique par nom. Après avoir trié les données par note, vous pouvez voir que l'ordre alphabétique des noms a été conservé pour chaque ligne avec la même note.

Avec un tri instable, il n'y a aucune garantie que l'ordre alphabétique soit conservé comme indiqué dans l'image ci-dessus.

Vous n'avez pas toujours besoin d'un tri stable

Il est particulièrement important de savoir si le tri que vous utilisez est stable ou non. Surtout dans les situations où vos données ont déjà un ordre que vous souhaitez conserver lorsque vous les triez par une autre clé de tri. Par exemple, vous avez des lignes dans une feuille de calcul contenant des données d'élève qui sont, par défaut, triées par nom. Vous souhaitez également le trier par notes tout en conservant l'ordre de tri des noms.

D'autre part, la stabilité du tri n'a pas d'importance lorsque les clés de tri des objets d'une collection sont les objets eux-mêmes - un tableau d'entiers ou de chaînes, par exemple - car nous ne pouvons pas faire la différence entre les objets dupliqués clés.

// JavaScript
// $5 bucks if you can correctly tell which 4 in the sorted// array was the first 4 when the array was unsorted.
var numbers = [5, 4, 3, 4, 9];numbers.sort(); // [3, 4, 4, 5, 9]
// A one second trip around the world, courtesy of the Flash, to// whomever correctly tells me which 'harry' in the sorted array was// the second 'harry' in the unsorted array.
var names = ['harry', 'barry', 'harry', 'cisco'];names.sort(); // ['barry', 'cisco', 'harry', 'harry']

Les sortes sont partout - connaissez vos sortes

Il est assez facile de savoir si le tri par défaut dans votre langage de programmation ou bibliothèque est stable. La documentation doit inclure ces informations. Par exemple, le tri par défaut est stable en Python, instable en Ruby et indéfini? en JavaScript (cela dépend de l'implémentation du navigateur).

Voici quelques algorithmes de tri courants et leur stabilité:

  • Tri par insertion - Stable
  • Tri de sélection - instable
  • Tri à bulles - Stable
  • Tri de fusion - Stable
  • Tri Shell - Instable
  • Timsort - Stable

Voir Wikipedia pour une liste plus exhaustive.

C'est l'heure de la démonstration? ‍?

Cette démo montre l'effet de l'utilisation d'un algorithme de tri stable (tri par insertion) et instable (tri par sélection) pour trier une petite table de données. Je me suis un peu amusé et j'ai pratiquement inversé React lors de la construction. Jetez un œil à la source.

Et après?

Si vous avez soif de plus de connaissances sur la stabilité d'autres algorithmes de tri, Wikipedia a un bon tableau de comparaison et des informations supplémentaires sur les algorithmes de tri bien connus.

Jusqu'à la prochaine fois, la paix.

Vous avez appris quelque chose de nouveau ou aimé lire cet article? Appliquez-le?, Partagez-le pour que les autres puissent lire aussi, et suivez pour plus. N'hésitez pas à laisser un commentaire aussi.