Qu'est-ce que cela signifie pour un algorithme de tri d'être «stable»?
43
En lisant divers algorithmes de tri, j'ai vu qu'il était mentionné que certains étaient "stables" et d'autres non. Qu'est-ce que cela signifie et quels compromis sont impliqués sur cette base lors de la sélection d'un algorithme?
C'est une question qui manque de recherche propre. Répondu avec une image wikipedia. Et cela génère de très bons retours, ce qui me rend triste. IMHO il devrait être fermé, et ne pas obtenir des votes positifs.
Mare Infinitus
4
D'autre part, je viens de voir cela et d'apprendre quelque chose de nouveau. Si j'avais su que je ne le savais pas, j'aurais pu faire des recherches, mais parce que le PO a posé la question, je sais maintenant ce que je ne savais pas que je ne savais pas.
Kazark
4
En règle générale, "ne faites que google" ou "consultez-le sur wikipedia" ne constitue pas une réponse très acceptable sur les sites StackExchange. Parce qu'ils ne fournissent pas de réponse à ce que le plaignant vérifie comme une question valide avec l'appel des autorités de Google et de Wikipédia. Si la question est facilement une copie d'une autre question ou de questions de programmers.stackexchange, vous pouvez vous plaindre.
Michael Paulukonis
Réponses:
88
Une sorte stable est une sorte qui préserve l'ordre d'origine du jeu d'entrées, où l'algorithme de comparaison ne fait pas la distinction entre deux ou plusieurs éléments.
Considérons un algorithme de tri qui trie les cartes par rang mais pas par couleur. La sorte stable garantira que l’ordre initial des cartes ayant le même rang est préservé; la sorte instable ne sera pas.
Correction: l'algorithme instable présente un comportement indéfini lorsque deux éléments sont égaux, il est parfaitement possible que l'ordre soit parfois préservé.
@MareInfinitus: C'est dans le domaine public. Vérifiez l'attribution sur l'image d'origine.
Robert Harvey
2
Une bonne image explique plus rapidement et plus profondément que beaucoup de mots dans l’affaire moyenne. Les questions juridiques n'étaient pas ce dont je voulais parler.
Mare Infinitus
3
@ RobertHarvey En fait, je pense que l'éditeur a raison. Votre message indique actuellement qu'un tri stable conserve l'ordre de classement des cartes de la même couleur, mais que les cartes de la même couleur auront des rangs différents et doivent donc être réorganisées pour que l'ordre soit trié. Par exemple, le tri ne conserve pas l'ordre des 2 et des 5 de cœur. C'est la commande de cartes de même rang (et de couleurs différentes) qui fait la différence entre stable et instable.
David Z
26
Les algorithmes stables préservent l'ordre relatif des éléments.
Ainsi, un algorithme de tri stable conservera l'ordre relatif des valeurs qui se comparent de manière égale.
Considérons un algorithme de tri dans lequel nous trions une collection de points 2D en fonction de leur dimension X.
En ce qui concerne le compromis ... eh bien, le tri stable est moins efficace, mais parfois vous en avez besoin.
Par exemple, lorsqu'un utilisateur clique sur l'en-tête d'une colonne pour trier les valeurs dans une interface utilisateur, il est raisonnable de s'attendre à ce que son ordre de tri précédent soit utilisé dans le cas de valeurs égales.
Est-ce moins efficace cependant? Cela semble "évident", mais certains des meilleurs algorithmes de tri sont par nature stables (par exemple, tout ce qui est basé sur le tri par fusion, tel que le tri de Tim), il n’est pas nécessaire de faire un travail supplémentaire explicite pour être stable.
9
Stable n'a rien à voir avec la performance en général. Mergesort s'exécute en O (n * log n) et est stable. Heapsort a des performances similaires mais n'est pas stable.
Mare Infinitus
2
"Stable" peut également s'appliquer aux structures de données, par exemple. Un "tas stable" est un tas qui met en file d'attente les éléments qui ont la même priorité dans le même ordre dans lequel ils ont été mis en file d'attente. Ceci est très important pour des algorithmes de recherche de chemin efficaces.
BlueRaja - Danny Pflughoeft
1
Il n'y a pas de sortes stables qui sont des comparaisons O (n ln n) et aussi O (1) sur la mémoire. La vitesse n'est pas la seule mesure de l'efficacité. Le fait que vous ne puissiez pas trier de manière stable est important.
QuestionC
3
@QuestionC Il semble que le tri par bloc soit stable et s’adapte à ces limites.
Réponses:
Une sorte stable est une sorte qui préserve l'ordre d'origine du jeu d'entrées, où l'algorithme de comparaison ne fait pas la distinction entre deux ou plusieurs éléments.
Considérons un algorithme de tri qui trie les cartes par rang mais pas par couleur. La sorte stable garantira que l’ordre initial des cartes ayant le même rang est préservé; la sorte instable ne sera pas.
la source
Les algorithmes stables préservent l'ordre relatif des éléments.
Ainsi, un algorithme de tri stable conservera l'ordre relatif des valeurs qui se comparent de manière égale.
Considérons un algorithme de tri dans lequel nous trions une collection de points 2D en fonction de leur dimension X.
Collection à trier:
{(6, 3), (5, 5), (6, 1), (1, 3)}Stable Trié:
{(1, 3), (5, 5), (6, 3), (6, 1)}Ordonné Trié:
{(1, 3), (5, 5), (6, 3), (6, 1)}ou{(1, 3), (5, 5), (6, 1), (6, 3)}En ce qui concerne le compromis ... eh bien, le tri stable est moins efficace, mais parfois vous en avez besoin.
Par exemple, lorsqu'un utilisateur clique sur l'en-tête d'une colonne pour trier les valeurs dans une interface utilisateur, il est raisonnable de s'attendre à ce que son ordre de tri précédent soit utilisé dans le cas de valeurs égales.
la source