Quel est l'avantage pour un algorithme de tri pour être stable?
Un tri est dit 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.
Vous devez vous connecter pour publier un commentaire.
Il permet à votre sorte de "chaîne" à travers de multiples conditions.
Dire 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:
Seront garantis pour être dans le bon ordre.
De Stable Algorithmes De Tri
Une file d'attente de priorité, en est un exemple. Disons que vous avez ceci:
Si vous triez ce du plus petit au plus grand nombre, un tri instable pourrait le faire.
...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.
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 préservé.
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:
Qui est ce que je veux, ou je pourrais retrouver avec ceci:
(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.
Un exemple:
Dire que vous avez une structure de données qui contient des paires de numéros de téléphone et les employés qui les a appelés. Un certain nombre/enregistrement de l'employé est ajouté après chaque appel. Certains numéros de téléphone peuvent être appelés par plusieurs employés.
En outre, supposons que vous souhaitez trier la liste par numéro de téléphone et de donner un bonus pour les 2 premières personnes qui ont appelé un nombre donné.
Si vous triez avec une instabilité de l'algorithme, vous ne pouvez pas conserver l'ordre des appelants d'un nombre donné, et le mauvais employés pourraient avoir le bonus.
Un algorithme stable permet de s'assurer que le droit à 2 personnes par numéro de téléphone obtenir le bonus.
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.
Un cas, c'est quand vous voulez trier par plusieurs touches. Par exemple, pour trier une liste de prénom /nom paires, vous pouvez trier d'abord par le nom de la première, et ensuite par le nom de famille.
Si votre tri n'était pas stable, alors vous perdriez le bénéfice de la première sorte.
L'avantage de la stabilité de tri pour plusieurs touches est douteuse, vous pouvez toujours utiliser une comparaison qui compare toutes les touches à la fois. C'est seulement un avantage si vous êtes le tri d'un champ à un moment, que lorsque vous cliquez sur un en-tête de colonne - Joe Koberg donne un bon exemple.
Toute sorte peut être transformé en un tri stable si vous pouvez vous permettre d'ajouter un numéro de séquence de l'enregistrement, et l'utiliser comme un bris d'égalité lorsqu'ils sont présentés avec les mêmes touches.
Le plus grand avantage lorsque le document original a un sens en elle-même. Je ne pouvais pas trouver un bon exemple, mais je vois JeffH n'a alors que je pensais à ce sujet.
Disons que vous êtes le tri sur un jeu de données d'entrée qui a deux champs, et, vous ne le tri sur la première. Le caractère " | " divise les champs.
Dans le jeu d'entrée, vous avez beaucoup d'entrées, mais, vous avez 3 entrées qui ressemblent à des
.
.
.
AAA|remorquage
.
.
.
AAA|location de voiture
.
.
.
AAA|plomberie
.
.
.
Maintenant, quand vous obtenez fait le tri vous vous attendez à ce que tous les champs avec AAA dans leur ensemble.
Un tri stable, vous pouvez:
.
.
.
AAA|remorquage
AAA|location de voiture
AAA|plomberie
.
.
.
c'est à dire, les trois dossiers qui avait la même clé de tri, AAA, sont dans le même ordre dans la sortie qu'ils étaient dans l'entrée. Notez qu'ils ne sont pas triés sur le deuxième champ, parce que vous n'avez pas de tri sur le deuxième champ dans l'enregistrement.
Un tri instable, vous pouvez:
.
.
.
AAA|plomberie
AAA|location de voiture
AAA|remorquage
.
.
.
Noter que les enregistrements sont toujours triés uniquement sur le premier champ, et, de l'ordre de la
deuxième champ diffère de l'entrée de commande.
Un tri instable a le potentiel pour être plus rapide. Un tri stable tend à imiter ce que les non-informaticien/non-math gens ont dans leur tête quand ils sorte quelque chose. C'est à dire, si vous avez fait un tri d'insertion avec les cartes d'index, vous serait le plus susceptible d'avoir un tri stable.
Vous ne pouvez pas toujours de comparer tous les champs à la fois. Quelques exemples: (1) les limites de la mémoire, où vous êtes le tri d'un grand fichier de disque, et il n'y a pas de place pour tous les champs de tous les enregistrements dans la mémoire principale; (2) le Tri d'une liste de la classe de base des pointeurs, où certains objets peuvent être dérivées sous-classes (vous avez seulement accès à la classe de base des champs).
Aussi, stable sortes ont déterministe de sortie donné la même entrée, qui peut être important pour le débogage et de test.