Qu'est-ce que la stabilité dans les algorithmes de tri et pourquoi est-elle importante ?

Question

Je suis très curieux de savoir pourquoi la stabilité est ou n'est pas importante dans les algorithmes de tri ?

Answer 1

Un algorithme de tri est dit stable si deux objets ayant des clés égales apparaissent dans le même ordre dans la sortie triée que dans le tableau non trié d'entrée. Certains algorithmes de tri sont stables par nature, comme le tri par insertion, le tri par fusion, le tri à bulles, etc. Et certains algorithmes de tri ne le sont pas, comme le tri par tas, le tri rapide, etc.

Cependant, tout algorithme de tri qui n'est pas stable peut être modifié pour le devenir. Il peut y avoir des moyens spécifiques à l'algo de tri pour le rendre stable, mais en général, tout algorithme de tri basé sur la comparaison qui n'est pas stable par nature peut être modifié pour le devenir en changeant l'opération de comparaison des clés de sorte que la comparaison de deux clés considère la position comme un facteur pour les objets ayant des clés égales.

Références : http://www.math.uic.edu/~leon/cs-mcs401-s08/handouts/stability.pdf http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

Answer 2

Je sais qu'il y a beaucoup de réponses à cela, mais pour moi, cette réponse par Robert Harvey a résumé la situation de manière beaucoup plus claire :

Un tri stable est un tri qui préserve l'ordre original de l'ensemble d'entrée, alors que l'algorithme [instable] ne fait pas de distinction entre deux ou plusieurs éléments.

Source :

Answer 3

Quelques exemples supplémentaires de la raison pour laquelle on veut des sortes stables. Les bases de données sont un exemple courant. Prenons le cas d'une base de données de transactions comprenant le nom et le prénom, la date et l'heure d'achat, le numéro d'article et le prix. Supposons que la base de données soit normalement triée par date et heure. Puis une requête est faite pour faire une copie triée de la base de données par nom de famille et prénom, puisqu'un tri stable préserve l'ordre d'origine, même si la comparaison de la requête ne concerne que le nom de famille et prénom, les transactions pour chaque nom de famille et prénom seront dans l'ordre date/heure.

Un exemple similaire est l'Excel classique, qui limite les tris à 3 colonnes à la fois. Pour trier 6 colonnes, un tri est effectué sur les 3 colonnes les moins significatives, suivi d'un tri sur les 3 colonnes les plus significatives.

Un exemple classique de tri radix stable est un trieur de cartes, utilisé pour trier un champ de colonnes numériques en base 10. Les cartes sont triées du chiffre le moins significatif au chiffre le plus significatif. À chaque passage, un jeu de cartes est lu et séparé en 10 cases différentes en fonction du chiffre de cette colonne. Ensuite, les 10 bacs de cartes sont remis dans l'ordre dans la trémie d'entrée (cartes "0" en premier, cartes "9" en dernier). Puis un autre passage est effectué par la colonne suivante, jusqu'à ce que toutes les colonnes soient triées. Les trieuses de cartes réelles ont plus de 10 cases car il y a 12 zones sur une carte, une colonne peut être vide et il existe une case pour les erreurs de lecture. Pour trier des lettres, 2 passages par colonne sont nécessaires, le 1er passage pour le chiffre, le 2ème passage pour la zone 12 11.

Plus tard (1937), il existait des machines à assembler (fusionner) les cartes qui pouvaient fusionner deux jeux de cartes en comparant les champs. L'entrée était constituée de deux jeux de cartes déjà triés, un jeu principal et un jeu secondaire. L'assembleuse fusionnait les deux jeux dans un nouveau bac principal et un bac d'archives, qui était éventuellement utilisé pour les doublons du maître, de sorte que le nouveau bac principal ne contienne que des cartes de mise à jour en cas de doublons. C'est probablement la base de l'idée derrière le tri par fusion (ascendant) original.

Answer 4

Si l'on part du principe que les éléments à trier ne sont que des nombres et que seules leurs valeurs les identifient/distinguent (par exemple, des éléments ayant la même valeur sont identiques), alors la question de la stabilité du tri n'a pas de sens.

Cependant, les objets ayant la même priorité de tri peuvent être distincts, et parfois leur ordre relatif constitue une information significative. Dans ce cas, le tri instable génère des problèmes.

Par exemple, vous avez une liste de données qui contient le coût en temps [T] de tous les joueurs pour nettoyer un labyrinthe de niveau [L] dans un jeu. Supposons que nous devions classer les joueurs en fonction de la vitesse à laquelle ils nettoient le labyrinthe. Toutefois, une règle supplémentaire s'applique : les joueurs qui nettoient le labyrinthe avec un niveau supérieur ont toujours un rang plus élevé, quelle que soit la durée du nettoyage.

Bien entendu, vous pouvez essayer de faire correspondre la valeur appariée [T,L] à un nombre réel [R] à l'aide d'un algorithme qui respecte les règles, puis classer tous les joueurs en fonction de la valeur [R].

Toutefois, si un tri stable est possible, vous pouvez simplement trier la liste entière par [T] (les joueurs les plus rapides d'abord) et ensuite par [L]. Dans ce cas, l'ordre relatif des joueurs (par coût en temps) ne sera pas modifié après que vous les ayez regroupés par niveau de labyrinthe qu'ils ont nettoyé.

PS : bien sûr, l'approche consistant à trier deux fois n'est pas la meilleure solution au problème particulier, mais pour expliquer la question de l'affichage, elle devrait suffire.

Answer 5

Un tri stable renvoie toujours la même solution (permutation) pour une même entrée.

Par exemple, [2,1,2] sera trié en utilisant le tri stable comme permutation [2,1,3] (d'abord l'index 2, puis l'index 1 et enfin l'index 3 dans la sortie triée). Cela signifie que la sortie est toujours mélangée de la même façon. Une autre permutation non stable, mais toujours correcte, est [2,3,1].

Le tri rapide n'est pas un tri stable et les différences de permutation entre les mêmes éléments dépendent de l'algorithme de sélection du pivot. Certaines implémentations choisissent le pivot au hasard et cela peut faire que le tri rapide donne des permutations différentes sur la même entrée en utilisant le même algorithme.

L'algorithme de tri stable est nécessairement déterministe.