Pourquoi Selection sort peut être stable ou instable

Je sais que selection sort peut être mis en œuvre comme stable ou instable. Mais je me demande comment il peut être. Je pense que l'algorithme de tri peut seulement être stable ou instable. Quelqu'un peut m'expliquer?

source d'informationauteur fortegente

  1. 40

    Essentiellement dans selection sortswap qui se produit à la fin de chaque "round" peut changer l'ordre relatif des éléments ayant la même valeur.

    par exemple, supposons que vous triées 4 2 3 4 1 avec selection sort.

    le premier "round" va passer par chaque élément de la recherche de l'élément minimum. il va trouver que 1 est l'élément minimum. puis il échange les 1 dans la première place. ce sera la cause de la 4 dans le premier endroit où aller dans le dernier spot: 1 2 3 4 4

    maintenant l'ordre relatif des 4 a changé. la "première" 4 dans la liste initiale a été déplacé à un endroit après l'autre 4.

    rappelez-vous la définition de la stabilité est que

    l'ordre relatif des éléments ayant la même valeur est maintenue.

    Bien, selection sort œuvres par trouver les "moins" à valeur dans un ensemble de valeurs, puis il échange avec la première valeur:

    Code:

    2, 3, 1, 1 # analyse, de 0 à n et de trouver "moins de" valeur

    1, 3, 2, 1 # swap "moins" avec l'élément 0.

    1, 3, 2, 1 # analyse de 1 à n et de trouver "moins de" valeur

    1, 1, 2, 3 # swap "moins" avec l'élément 1.

    ...et ainsi de suite jusqu'à ce qu'elle est triée.

    Pour faire de cet stable, au lieu de swaping valeurs, insérez le "moins" de la valeur plutôt que:

    Code:

    2, 3, 1, 1 # analyse, de 0 à n et de trouver "moins de" valeur

    1, 2, 3, 1 # insert 'moins' au pos 0, poussant d'autres éléments.

    1, 3, 2, 1 # analyse de 1 à n et de trouver "moins de" valeur

    1, 1, 2, 3 # insert 'moins' au pos 1, poussant d'autres éléments.

    ...et ainsi de suite jusqu'à ce qu'elle est triée.

    Il ne devrait pas être trop dur à modifier l'instabilité de sélection de l'algorithme de tri à devenir stable.

  2. 18

    En commun des cas, vous n'êtes pas correct. Sélection de tri est instable. Que vient-il de la définition. Donc, vous êtes évidemment confondu avec un boîtier personnalisé.

    Il peut être stable - normalement, seulement avec les listes liées. Faire (façon classique, O(1) de la mémoire) - au lieu de swaps, d'minimale de l'élément doit être liée à la ménagères de la partie, rendant l'ensemble de l'algorithme stable. Et c'est la différence de "mise en œuvre" - ce qui, évidemment, va produire de la stabilité dans ce cas seulement en raison de la structure de données spécifiques. Il n'a rien à voir avec le cas le plus courant, lors de la sélection, le tri est instable

  3. 4

    Disons que j'ai ce tableau:

    A = {3, 3, 1}

    En commençant à la position 0, la sélection de tri va chercher la valeur minimale et permuter l'élément en cours avec le minimum. Pour Aon échange la première 3 avec 1et de ne rien faire sur la deuxième étape.

    Ce n'est pas stable car la première 3 aurait du venir avant le second. Si vous utilisez une liste liée au lieu d'un tableau, et insérer un élément dans la position correcte au lieu d'échange, de sélection, de tri est stable.

  4. 0

    Le fait qu'un tri d'acheminement est une sélection de tri ne définit pas tout à ce sujet. Il y a encore des décisions à prendre qui pourrait être fait différemment dans les différentes implémentations, et des choix différents peuvent produire un stable ou instable de tri. (La plupart des espèces qui peuvent être stables n'ont pas à être; en général, l'théorique intéressant question est de savoir si le tri peut être mis en œuvre de façon stable.)