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

un algorithme de tri stable est celui qui trie les éléments identiques dans le même ordre qu'ils apparaissent dans l'entrée, tandis que le tri instable ne peut pas satisfaire le cas.

Algorithmes De Tri Stables:

• Insertion Tri
• Fusion Tri
• Tri À Bulles
• Tim Sort
• Counting Trier

Algorithmes De Tri Instables:

• Tas De Tri
• tri de sélection
• tri de Shell
• Tri Rapide

stabilité de tri signifie que les enregistrements avec la même clé conservent leur ordre relatif avant et après le tri.

donc la stabilité importe si, et seulement si, le problème que vous résolvez nécessite le maintien de cet ordre relatif.

si vous n'avez pas besoin de stabilité, vous pouvez utiliser un algorithme rapide de mémorisation à partir d'une bibliothèque, comme heapsort ou quicksort, et l'oublier.

Si vous avez besoin de stabilité, c'est plus compliqué. Les algorithmes stables ont une plus grande utilisation du processeur big-O et / ou de la mémoire que les algorithmes instables. Donc, quand vous avez un ensemble de données de grande taille, vous devez choisir entre battre le CPU ou la mémoire. Si vous êtes limité à la fois sur le CPU et la mémoire, vous avez un problème. Un bon algorithme stable de compromis est un tri d'arbre binaire; L'article de Wikipedia a une implémentation C++ pathétiquement facile basée sur le STL.

vous pouvez transformer un algorithme instable en un algorithme stable par ajouter le numéro d'enregistrement original comme touche de la dernière place pour chaque enregistrement.

Cela dépend de ce que vous faites.

Imaginez que vous avez des dossiers de personnes avec un prénom et un nom de famille. D'abord, vous triez la liste par prénom. Si vous triez ensuite la liste avec un algorithme stable par nom de famille, vous aurez une liste triée par prénom et nom de famille.

il y a quelques raisons pour lesquelles la stabilité peut être importante. La première est que, si deux enregistrements n'ont pas besoin d'être échangés en les échangeant, vous pouvez provoquer une mise à jour de la mémoire, une page est marquée "sale", et doit être réécrite sur disque (ou un autre médium lent).

un algorithme de tri est dit stable si deux objets avec des clés égales apparaissent dans le même ordre dans la sortie triée comme ils apparaissent dans le tableau d'entrée non triée. Certains algorithmes de tri sont stables par nature comme tri D'Insertion, tri de fusion, tri de bulle, etc. Et certains algorithmes de tri ne sont pas, comme le tri en tas, le tri rapide, etc.

cependant, toute algue de tri donnée qui n'est pas stable peut être modifiée pour être stable. Il peut y avoir des moyens spécifiques de le faire 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 être stable en changeant l'opération de comparaison de clés de sorte que la comparaison de deux clés considère la position comme un facteur pour les objets avec 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

je sais qu'il y a beaucoup de réponses, mais pour moi, cette réponse , par Robert Harvey , résume beaucoup plus clairement:

une sorte stable est une sorte qui préserve l'ordre original de l'ensemble d'entrée, où l'algorithme [unstable] ne distingue pas entre deux ou plusieurs éléments.

Source

si vous supposez que ce que vous triez ne sont que des nombres et que seules leurs valeurs les identifient/les distinguent (par exemple, les éléments avec la même valeur sont identiticle), alors la question de la stabilité du tri est dénuée de sens.

cependant, les objets ayant la même priorité dans le tri peuvent être distincts, et parfois leur ordre relatif est une information significative. Dans ce cas, unstable sort génère des problèmes.

Par exemple, vous avez une liste de données qui contient les temps [T] de tous les joueurs pour nettoyer un labyrinthe avec le niveau [L] dans un jeu. Supposons que nous avons besoin de classer les joueurs par la vitesse à laquelle ils nettoient le labyrinthe. Cependant, une règle supplémentaire s'applique: les joueurs qui nettoient le labyrinthe avec un niveau plus élevé ont toujours un rang plus élevé, peu importe combien de temps le coût est.

bien sûr,vous pourriez essayer de mapper la valeur de paire [T, L] à un nombre réel [R] avec un algorithme qui suit les règles et puis classer tous les joueurs avec la valeur [R].

cependant, si le tri stable est possible, alors vous pouvez simplement trier la liste entière par [T] (lecteurs plus rapides d'abord) et ensuite par [l]. Dans ce cas, l'ordre relatif des joueurs (par coût de 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 pour trier deux fois n'est pas la meilleure solution au problème particulier, mais pour expliquer la question de l'affiche, il devrait être suffisant.

le tri Stable retournera toujours la même solution (permutation) sur la même entrée.

par exemple [2,1,2] sera trié en utilisant le tri stable comme permutation [2,1,3] (d'abord l'indice 2, puis l'indice 1, puis l'indice 3 dans la sortie triée) ce qui signifie que la sortie est toujours mélangée de la même manière. Autre permutation non stable, mais encore correcte est [2,3,1].

Quick sort n'est pas stable sort et les différences de permutation entre les mêmes éléments dépend de l'algorithme pour pivot de prélèvement. Certaines implémentations ramassent au hasard et cela peut faire un tri rapide donnant différentes permutations sur une même entrée en utilisant le même algorithme.

l'algorithme de tri Stable est nécessaire déterministe.