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

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

  • Pour la parallélisation des fins? par exemple: fusion de tri est stable et peut être parallélisée bien et est donc quicksort.
  • Classique QuickSort est instable
  • tri stable algo - IBM (Insertion, Bubble, Merge)
  • excusez-moi?
  • Une remarque pour ceux qui pourraient mal compris le concept comme moi: L'ordre des éléments égaux est assuré d'être préservé. moyens: si les éléments stables de tri sont considérés comme égaux, alors ils suivent la commande précédente. pas ce que j'ai l'habitude de penser: si les éléments dans l'ordre précédent, sont considérés comme égaux, puis dans les prochains tri stable, ils suivent la commande précédente. Si vous pouvez trouver la dernière acception aussi du sens dans de nombreux cas.
InformationsquelleAutor DarthVader | 2009-10-05
  1. 299

    Un algorithme de tri est dit être stable si deux objets avec l'égalité des clés apparaissent dans le même ordre de tri de sortie tels qu'ils apparaissent dans le tableau à trier. Certains algorithmes de tri sont stables par nature, comme le tri par Insertion, de Fusion et de Tri, Tri à Bulles, etc. Et certains algorithmes de tri ne sont pas, comme les Tas de Tri, Tri Rapide, etc.

    Fond: une "stabilité" algorithme de tri qui conserve les éléments avec la même clé de tri dans l'ordre. Supposons que nous avons une liste de 5 lettres les mots:

    peach
straw
apple
spork

    Si nous trier la liste par juste la première lettre de chaque mot, puis un stable de sorte donnerait:

    apple
peach
straw
spork

    Dans un instable algorithme de tri, straw ou spork peuvent être confondus, mais dans une version stable, ils restent dans les mêmes positions relatives (qui est, depuis straw apparaît avant spork dans l'entrée, il apparaît aussi avant spork dans la sortie).

    On peut trier la liste des mots à l'aide de cet algorithme: stable tri par colonne 5, puis 4, puis 3, puis 2, puis 1.
    En fin de compte, il sera triée correctement. Laissez-vous convaincre de cela. (en passant, que l'algorithme est appelé tri radix)

    Maintenant pour répondre à votre question, supposons que nous avons une liste de noms et de prénoms. On nous demande de trier "par nom de famille, puis par la première". Nous pourrions tout d'abord trier (stable ou instable) par le nom de la première, puis tri stable par le dernier nom. Après ces sortes, la liste est principalement triées par ordre de nom de famille. Toutefois, lorsque les noms sont les mêmes, les premiers noms sont triés.

    Vous ne pouvez pas pile instable sortes de la même manière.

    • Sonne bien. D'autres raisons ?
    • Donc, ce serait de la sorte être appelé à prendre les mots dans le bon ordre de tri de la pomme pêche sportive de la paille? Le tri stable nous a donné la pomme pêche paille spork toutefois st devrait l'être après sp (par ordre alphabétique correct), donc, l'ultime tri correct devrait être pomme pêche sportive de la paille
    • Nous sommes le tri par la première lettre seulement. Avec cette hypothèse, straw et spork comparer l'égalité. Tri Stable à préserver l'ordre d'entrée, alors que le tri instable ne fait pas de cette garantie. "Correct" dépend de l'application. La fonction de tri dans la plupart des langages de programmation permet à l'utilisateur de fournir une coutume fonction de commande. Si l'utilisateur de la fonction de la traite différents articles comme des égaux (même prénom, nom de famille différent), il est utile de savoir si l'ordre original sera conservé. Voir OCaml matrice de fonctions de tri pour un exemple réel.
    • Je ne comprends pas la ligne ..même clé de tri ? Qu'entendez-vous par la clé ici ? Veuillez expliquer la déclaration de ..même clé de tri
    • par "clé de tri", je veux dire la chose à trier les objets par. Ainsi, lorsque le tri par la première lettre, puis, pour chaque objet, de sa "clé de tri" est sa première lettre.
    • J'ai juste ajouté un alinéa au début de votre réponse . j'espère que c'est ok avec vous. 🙂
    • Merci, semble bon!
    • Pouvez-vous s'il vous plaît ajouter les informations dans votre commentaire dans votre réponse. J'étais sur le point de down vote, c'est comme spork ne viennent avant straw, sauf si vous êtes seulement de tri par la première lettre. Pour moi ce n'est pas une façon naturelle de trier les chaînes et devrait être clair.
    • Je ne suis pas sûr de savoir comment le mot; l'esprit de donner un coup de feu? Je dis "stable-le tri par la première lettre", mais je suppose que c'est facile de parcourir plus de cela.
    • J'ai l'ajustez. J'ai fait sauter à droite sur l'endroit où vous l'avez dit trier en fonction de la première lettre. Je pense que cela pourrait attirer un peu plus d'attention à elle. Si vous ne l'aimez pas, juste de rouler de nouveau. Il est bon de toute façon, j'ai juste besoin de ralentir ma lecture. Merci.
    • si cela s'applique uniquement aux chaînes de caractères, des nombres, tous les algos sera stable?
    • Exemple Disons que vous avez une liste, chaque élément ayant des informations sur la destination du vol et l'heure de départ. Vous d'abord trier la liste en fonction du temps. Nous avons ensuite les trier en fonction de votre destination. Si le deuxième type est stable nous avons maintenant tous les vols liés à la même destination, ensemble et dans l'ordre croissant de leur heure de départ. Si elle n'était pas stable, il ne sera pas dans l'ordre croissant de temps.
    • d'accord avec la réponse et l'explication

    InformationsquelleAutor Joey Adams
  2. 42

    Stable algorithme de tri est celui qui trie les éléments identiques dans le même ordre qu'elles apparaît dans l'entrée, tandis que instables tri peut pas satisfaire le cas.

    Stable Algorithmes De Tri:

    • Le Tri Par Insertion
    • De Fusion Tri
    • De Tri À Bulles
    • Tim Sorte
    • Comptage Tri

    Instable Algorithmes De Tri:

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

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

    • Vos valeurs ne sont pas égales. Vous comparez 9,7 et 9,8 mais selon du contrôle de stabilité, vous devez les mêmes valeurs comme 9,7 ou les deux 9,8. Et que même les valeurs doivent être commandés en même dans la stabilité des algorithmes.
    • Non, pour vérifier la stabilité de vos valeurs doivent être identiques. Je veux dire, supposons que vous utilisez deux 9,7 et nommez à des nœuds A et B. Si chaque opération de tri de l'ordre, c'est comme A,B (au lieu de ils sont égaux) comprendre que l'algorithme de tri est stable(comme la fusion de tri). Si A, B commande de changement lorsque les trier en plusieurs fois(1. tri de A,B puis B,Un nouveau A,B, etc), comprendre que l'algorithme de tri est instable(comme le tri rapide) @snr
    • 6] n'est pas présent dans le Tableau d'Entrée. Je pense que vous vouliez dire, [9, 8] dans le dernier tableau de la bande.
    • Je crois qu'il est le tri par le premier nombre (celle d'avant la virgule) et à l'aide de la deuxième numéro, juste une référence pour vous de voir que la première 9 est différent de celui de la seconde à 9.
    • merci pour les précisions, oui, il a du sens.
    InformationsquelleAutor snr
  3. 18

    De tri de la stabilité signifie que les enregistrements ayant la même clé de conserver leur commande avant et après le tri.

    Alors la stabilité des questions si, et seulement si, le problème que vous avez des problèmes exige de rétention de l'ordre relatif.

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

    Si vous avez besoin de stabilité, c'est plus compliqué. Stable algorithmes ont plus grand-O CPU et/ou de l'utilisation de la mémoire que instables algorithmes. Ainsi, lorsque vous avez un grand ensemble de données, vous avez à choisir entre vaincre le CPU ou de la mémoire. Si vous êtes limité sur les deux CPU et de la mémoire, vous avez un problème. Un bon compromis stable algorithme est un arbre binaire de tri; l' Article de Wikipedia a un pathétiquement facile implémentation C++ basé sur la STL.

    Vous pouvez faire de l'instabilité de l'algorithme dans un stable par l'ajout de l'enregistrement d'origine numéro de la dernière place de la clé pour chaque enregistrement.

    • Stable algorithmes comme la Fusion de l'eiso ont le même O(NlogN) la complexité en tant que Quicksort; la constante multiplicateur de l'effort est plus grand, cependant.
    • Oui, et l'utilisation de la mémoire sur la Fusion de Tri en O(N), tandis que sur Quicksort il est O(log N). La raison je l'ai mentionné Quicksort est que qsort() est une bibliothèque C standard de routine, il est donc reaily disponibles.
    • reaily -> facilement
    • Meilleure réponse à mon humble avis. le multi-touche technique mentionné dans d'autres est intéressante mais surfait; il est simple à appliquer, mais elle tend à être beaucoup plus lent que les solutions de rechange évidentes (il suffit d'utiliser un tri avec un multi-touches comparer; ou triez les par la première clé, puis d'identifier et de trier toutes les sous-listes avec des doublons). Le fait que le tri stable produit un résultat prévisible peut être important dans certaines applications. En particulier si vous avez deux listes A,B, qui sont identiques à l'exception de la liste B a une entrée supplémentaire, les sorties pour un tri stable sera identique à l'exception de B a la même entrée supplémentaire. Et +1 pour la dernière pgph.
    InformationsquelleAutor Bob Murphy
  4. 15

    Il y a peu de raisons de stabilité peut être important. L'une est que, si deux enregistrements ne doivent pas être échangé en échangeant entre eux, vous pouvez provoquer un mémoire de mise à jour, une page est marqué sale et doit être ré-écrite sur le disque (ou un autre lent, moyen).

    InformationsquelleAutor Clinton Pierce
  5. 14

    Cela dépend de ce que vous faites.

    Imaginez que vous avez certaines personnes enregistrements avec un premier et un dernier champ nom. D'abord de trier la liste par nom de famille. Ensuite, si vous le tri de la liste avec un algorithme stable par nom de famille, vous aurez une liste triée par nom ET prénom.

    • Je pense que tu veux dire "dernier ET prénom". Le nom de famille est en général le nom de famille.
    InformationsquelleAutor svens
  6. 4

    Un algorithme de tri est dit stable si deux objets avec l'égalité des clés apparaissent dans le même ordre de tri de sortie tels qu'ils apparaissent dans l'entrée des ménagères de tableau. Certains algorithmes de tri sont stables par nature, comme le tri par Insertion, de Fusion et de Tri, Tri à Bulles, etc. Et certains algorithmes de tri ne sont pas, comme les Tas de Tri, Tri Rapide, etc.

    Cependant, tout algo de tri qui n'est pas stable peut être modifié pour être stable. Il peut y avoir des algo de tri des moyens spécifiques pour le rendre stable, mais en général, toute comparaison basée algorithme de tri qui n'est pas stable, par nature, peut être modifié pour être stable par changement de la clé de l'opération de comparaison, de sorte que la comparaison de deux touches considère position en tant que facteur d'objets avec l'égalité des touches.

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

    InformationsquelleAutor roottraveller
  7. 3

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

    Un tri stable est celle qui préserve l'ordre original du jeu de données d'entrée, où l' [instable] algorithme ne fait pas de distinction entre deux éléments ou plus.

    Source

    InformationsquelleAutor John R Perry
  8. 1

    Si vous assumez ce que vous êtes de tri sont seulement des nombres et seulement leurs valeurs identifier et de les distinguer (p. ex. les éléments avec la même valeur sont identicle), alors la stabilité de la question de triage vide de sens.

    Toutefois, les objets avec la même priorité dans le tri peut être distincts, et parfois leur ordre relatif est de l'information significative. Dans ce cas, l'instabilité de tri génère des problèmes.

    Par exemple, vous avez une liste de données qui contient le coût du 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 autre règle s'applique: les joueurs qui nettoient le labyrinthe de haut niveau ont toujours un rang plus élevé, peu importe combien de temps le coût du temps est.

    Bien sûr, vous pouvez essayer de mapper les paires de valeur [L,L] pour un nombre réel [R] avec un algorithme qui suit les règles et ensuite classer tous les joueurs avec [R] de la valeur.

    Toutefois, si stable que le tri est possible, alors vous pouvez simplement trier la liste par [T] (joueurs plus Rapides en premier), puis par [L]. Dans ce cas, l'ordre relatif des joueurs (par le temps, coût) ne pourront être modifiés une fois regroupés par niveau de labyrinthe, ils ont nettoyé.

    PS: bien sûr, l'approche de trier par deux fois n'est pas la meilleure solution au problème en particulier, mais pour expliquer la question de l'affiche, il devrait être suffisant.

    InformationsquelleAutor M Ciel
  9. 0

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

    Par exemple [2,1,2] seront triés à l'aide de tri stable que la permutation de [2,1,3] (la première est d'indice 2, puis à l'indice 1 indice, puis 3 dans triés en sortie) Qui signifie que la sortie est toujours mélangé de la même manière. D'autres non stable, mais toujours correct permutation est [2,3,1].

    Tri rapide n'est pas stable, de tri et de permutation des différences entre les mêmes éléments dépend de l'algorithme de pivot pour la cueillette. Certaines implémentations de ramasser au hasard et qui peut faire de rapide de tri de rendement de permutations différentes sur la même entrée en utilisant le même algorithme.

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

    • Ce n'est pas que de la stabilité. Voir en.wikipedia.org/wiki/Sorting_algorithm#Stability
    • Je devrait corriger la dernière phrase que non stable type de sortie différent de solution, même parmi même de la mise en œuvre, lorsqu'un tri stable sorties même solution.
    • Pourquoi -1 ? Quelqu'un peut-il point s'il vous plaît quel est le problème ici? Ce n'est pas ce de manière stable, le tri est, mais ce que la propriété stable tri a.
    • Si le tri est déterministe ou non ne permet pas de déterminer si elle est stable. Je peux écrire un non-stable déterministe de l'algorithme de tri par la définition d'un autre bris d'égalité-comportement (par subsorting non-éléments clés, par exemple). Tri Stable spécifiquement implique que la pré-triés de l'ordre relatif des éléments sont conservés lorsque les liens sont triés. exemple de sortie d'un tri stable: sort([(5,3),(1,5),(3,3),(1,3)], x) => [(1,5),(1,3),(3,3),(5,3)]. Je peux faire un déterministe sorte que toujours (approche déterministe) sorties: [(1,3),(1,5),(3,3),(5,3)] mais ce n'est pas un tri stable.
    • Il est plus relevé, à propos de nice de la propriété que chaque tri stable a. Qui n'est pas une question de sorcière stable algorithme de tri ou de la mise en œuvre est utilisé, chaque fois qu'il y aura même résultat. Il est plus difficile de maintenir ces biens entre les différents non stable de tri mises en œuvre.
    InformationsquelleAutor Luka Rahne