stabilité de l'algorithme de quicksort
Quicksort n'est pas stable, puisqu'il échange des éléments non adjacentes.
Merci de m'aider à mieux comprendre cette déclaration.
Je sais comment partitionnement fonctionne, et ce que la stabilité est. Mais je ne peux comprendre ce que fait le ci-dessus comme de raison pour que ce soit pas stable?
Alors je crois que la même chose peut être dit pour la fusion de tri mais il est cité à un algorithme stable.
source d'informationauteur IUnknown
Vous devez vous connecter pour publier un commentaire.
Considérer ce qui se passe au cours de la partition pour la suite de tableau de paires, où le comparateur utilise l'entier (seulement). La chaîne est juste là, de sorte que nous avons deux éléments qui permettent de comparer, comme si l'égalité, mais en fait, sont à distinguer.
Par définition, un tri est stable si, après le tri, les deux éléments qui permettent de comparer, comme si l'égalité (les deux
4
s) apparaissent dans le même ordre par la suite, comme ils le faisaient avant.Supposons que nous choisissons
3
que le pivot. Les deux4
éléments de fin d'après elle et la1
et la2
avant (il y a un peu plus que ça, je l'ai ignoré en déplaçant le pivot, puisqu'elle est déjà dans la bonne position, mais vous dites que vous comprenez partitionnement).Quicksorts en général ne donnent aucune garantie particulière où après la partition, les deux
4
s sera, et je pense que la plupart des implémentations serait inversé. Par exemple, si nous utilisons Hoare classique de l'algorithme de partitionnementle tableau est partitionné comme suit:qui viole la stabilité de tri.
Étant donné que chaque partition n'est pas stable, l'ensemble de la sorte n'est pas susceptible d'être.
Comme Steve314 souligne dans un commentaire, de fusion, le tri est stable à condition que lors de la fusion, si vous rencontrez des éléments égaux vous toujours en premier lieu la sortie de l'un qui est venu du "bas" de la deux moitiés que vous êtes fusionnent. C'est à chacun de fusion doit ressembler à ceci, où la "gauche" est le côté qui vient de plus bas dans le tableau d'origine.
Si le
<=
ont été<
puis la fusion ne serait pas stable.Il sera comme un utilisateur dispose d'un tableau trié, et trie par une autre colonne, ne l'algorithme de tri toujours de préserver l'ordre relatif des éléments qui diffèrent de la précédente clé de tri mais ont la même valeur dans la nouvelle clé de tri?
Donc, dans Un algorithme de tri qui a toujours conserve l'ordre des éléments (qui ne diffèrent pas dans la nouvelle clé de tri) est appelé un "tri stable".
Considérer la rangée suivante de paires:
{(4,'first');(2,'');(1,'');(4,'second');(3,'')}
Envisager de 3 comme pivot. Au cours d'une exécution du tri Rapide, le tableau subit des modifications suivantes:
{(4,'first');(2,'');(1,'');(4,'second');(3,'')}
{(2,'');(4,'first');(1,'');(4,'second');(3,'')}
{(2,'');(1,'');(4,'first');(4,'second');(3,'')}
{(2,'');(1,'');(3,'');(4,'second');(4,'first')}
{(1,'');(2,'');(3,'');(4,'second');(4,'first')}
Clairement de ce qui précède, l'ordre relatif est changé. C'est pourquoi le tri rapide est dit "de ne pas assurer la stabilité'.