Quel est l'avantage pour un algorithme de tri pour être stable?

Question

Une espèce est dite stable si elle maintient l'ordre relatif des éléments avec l'égalité des touches. Je suppose que ma question est vraiment, quel est l'avantage de maintenir l'ordre relatif? Quelqu'un peut-il donner un exemple? Merci.

Answer 1

Il permet à votre sorte de "chaîne" à travers de multiples conditions.

Disons que vous avez un tableau avec les noms et les prénoms dans un ordre aléatoire. Si vous triez par son prénom, puis par nom de famille, l'écurie algorithme de tri qui permettra de s'assurer que les personnes avec le même nom de famille sont triés par nom.

Par exemple:

• Smith, Alfred
• Smith, Zed

Seront garantis pour être dans le bon ordre.

Answer 2

Un algorithme de tri est stable si elle conserve l'ordre des doubles des clés.

OK, très bien, mais pourquoi cela devrait-il être important? Eh bien, la question de la "stabilité" dans un algorithme de tri qui se pose lorsque l'on souhaite trier les mêmes données plusieurs fois selon les différentes touches.

Parfois, les éléments de données clés multiples. Par exemple, peut-être un (unique) de la clé primaire tel qu'un numéro d'assurance sociale ou un numéro d'identification d'étudiant, et un ou plusieurs clés secondaires, telles que la ville de résidence, ou en laboratoire de la section. Et on peut très bien vouloir trier ces données selon plus d'un des clés. Le problème est que, si nous trier les données selon l'une des clés, et ensuite selon une deuxième clé, la deuxième clé peut détruire l'ordre obtenu par le premier tri. Mais cela n'arrivera pas si notre deuxième tri est un tri stable.

De Stable Algorithmes De Tri

Answer 3

Une file d'attente de priorité, en est un exemple. Disons que vous avez ceci:

1. (1, "bob")
2. (3, "la loi")
3. (1, "jane")

Si vous triez ce du plus petit au plus grand nombre, un tri instable pourrait le faire.

1. (1, "jane")
2. (1, "bob")
3. (3, "la loi")

...mais alors "jane" a l'avance "bob", même si il était censé être dans l'autre sens.

Généralement, ils sont utiles pour le tri des entrées multiples en plusieurs étapes.

Answer 4

Pas tous les tri est basé sur l'ensemble de la valeur. Tenir compte d'une liste de personnes. Je ne voulez trier par leurs noms, plutôt que l'ensemble de leurs informations. Stables avec un algorithme de tri, je sais que si j'ai deux personnes nommé "John Smith", puis leur ordre relatif va être conservé.

Last     First       Phone
-----------------------------
Wilson   Peter       555-1212
Smith    John        123-4567
Smith    John        012-3456
Adams    Gabriel     533-5574

Depuis les deux "John Smith"sont déjà "triés" (ils sont dans l'ordre, je les veux), je ne veux pas les faire changer de position. Si je tri de ces éléments en dernier, alors tout d'abord avec une instabilité de l'algorithme de tri, je pourrais terminer ce soit avec ceci:

Last     First       Phone
-----------------------------
Adams    Gabriel     533-5574
Smith    John        123-4567
Smith    John        012-3456
Wilson   Peter       555-1212

Qui est ce que je veux, ou je pourrais retrouver avec ceci:

Last     First       Phone
-----------------------------
Adams    Gabriel     533-5574
Smith    John        012-3456
Smith    John        123-4567
Wilson   Peter       555-1212

(Vous voyez les deux "John Smith"ont changé de place). Ce n'est PAS ce que je veux.

Si j'ai utilisé un stable algorithme de tri, je serais assuré d'obtenir la première option, qui est ce que je suis après.

Answer 5

Cela signifie que si vous souhaitez trier par Album ET par Numéro de Piste, vous pouvez cliquer sur le numéro de la Piste en premier, et c'est triée, puis cliquez sur le Nom de l'Album, et les numéros des pistes de rester dans le bon ordre pour chaque album.