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

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

Un algorithme de tri est dit stable si deux objets avec des clés égales apparaissent dans le même ordre en sortie triée comme ils apparaissent dans le tableau d'entrée à trier. Certains algorithmes de tri sont stables par nature comme le tri par insertion, le tri par fusion, le tri par bulles, etc. Et certains algorithmes de tri ne le sont pas, comme le tri par segments, le tri rapide, etc.

Contexte : un algorithme de tri "stable" conserve les éléments avec la même clé de tri dans l'ordre. Supposons que nous ayons une liste de mots de 5 lettres:

peach
straw
apple
spork

Si nous trions la liste en fonction de la première lettre de chaque mot, un tri stable produirait:

apple
peach
straw
spork

Dans un algorithme de tri instable , strawou sporkpeuvent être échangés, mais dans un algorithme stable, ils restent dans les mêmes positions relatives (c'est-à-dire, puisqu'apparaît strawavant sporkdans l'entrée, il apparaît également avant sporkdans la sortie).

On pourrait trier la liste des mots en utilisant cet algorithme: tri stable par colonne 5, puis 4, puis 3, puis 2, puis 1. Au final, il sera correctement trié. Convainquez-vous de cela. (à propos, cet algorithme est appelé tri radix)

Maintenant, pour répondre à votre question, supposons que nous ayons une liste de prénoms et de noms. On nous demande de trier "par nom, puis par prénom". Nous pourrions d'abord trier (stable ou instable) par le prénom, puis trier par le nom de famille. Après ces tris, la liste est principalement triée par nom de famille. Cependant, lorsque les noms de famille sont identiques, les prénoms sont triés.

Vous ne pouvez pas empiler des tris instables de la même manière.

Un algorithme de tri stable est celui qui trie les éléments identiques dans le même ordre qu'ils apparaissent dans l'entrée, tandis que le tri instable peut ne pas satisfaire le cas. - _{^{Je remercie mon professeur d'algorithme Didem Gozupek d'avoir fourni un aperçu des algorithmes}} .

Algorithmes de tri stables:

• Tri par insertion
• Tri par fusion
• Tri des bulles
• Tim Sort
• Tri par comptage
• Tri par bloc
• Quadsort
• Tri de bibliothèque
• Mélangeur à cocktail Sort
• Tri des gnomes
• Tri pair-impair

Algorithmes de tri instables:

• Tri par tas
• Tri de sélection
• Tri des coques
• Tri rapide
• Introsort (soumis à Quicksort)
• Tri des arbres
• Tri par cycle
• Smoothsort
• Tri par tournoi (soumis à Hesapsort)

La stabilité du tri signifie que les enregistrements avec la même clé conservent leur ordre relatif avant et après le tri.

La stabilité est donc importante si et seulement si le problème que vous résolvez nécessite le maintien de cet ordre relatif.

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

Si vous avez besoin de stabilité, c'est plus compliqué. Les algorithmes stables ont une utilisation du processeur Big-O et / ou de la mémoire plus élevée que les algorithmes instables. Donc, lorsque vous avez un grand ensemble de données, vous devez choisir entre battre le CPU ou la mémoire. Si vous êtes limité à la fois par le processeur et la mémoire, vous avez un problème. Un bon algorithme stable de compromis est un tri d'arbre binaire; l' article de Wikipedia a une implémentation pathétiquement facile C ++ basé sur la STL.

Vous pouvez transformer un algorithme instable en un algorithme stable en ajoutant le numéro d'enregistrement d'origine comme clé de dernière place pour chaque enregistrement.

Cela dépend de ce que vous faites.

Imaginez que vous avez des enregistrements de personnes avec un champ de prénom et un nom de famille. Vous triez d'abord la liste par prénom. Si vous triez ensuite la liste avec un algorithme stable par nom de famille, vous aurez une liste triée par prénom ET par nom de famille.

Il y a plusieurs raisons pour lesquelles la stabilité peut être importante. La première est que, si deux enregistrements n'ont pas besoin d'être échangés en les échangeant, vous pouvez provoquer une mise à jour de la mémoire, une page est marquée comme sale et doit être réécrite sur le disque (ou un autre support lent).

Un algorithme de tri est dit stable si deux objets avec des clés égales apparaissent dans le même ordre dans la sortie triée comme ils apparaissent dans le tableau d'entrée non trié. Certains algorithmes de tri sont stables par nature comme le tri par insertion, le tri par fusion, le tri par bulles, etc. Et certains algorithmes de tri ne le sont pas, comme le tri par segments, le tri rapide, etc.

Cependant, tout algo de tri donné qui n'est pas stable peut être modifié pour être stable. Il peut y avoir des moyens spécifiques de tri pour le rendre stable, mais en général, tout algorithme de tri basé sur la comparaison qui n'est pas stable par nature peut être modifié pour être stable en modifiant l'opération de comparaison de clés de sorte que la comparaison de deux clés considère la position comme un facteur pour les objets avec des clés égales.

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

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

Un tri stable est celui qui préserve l'ordre d'origine de l'ensemble d'entrée, où l'algorithme [unstable] ne fait pas de distinction entre deux ou plusieurs éléments.

La source

Si vous supposez que ce que vous triez ne sont que des nombres et que seules leurs valeurs les identifient / les distinguent (par exemple, les éléments de même valeur sont identiques), alors le problème de stabilité du tri n'a pas de sens.

Cependant, les objets avec la même priorité dans le tri peuvent être distincts, et parfois leur ordre relatif est une information significative. Dans ce cas, le tri instable génère des problèmes.

Par exemple, vous avez une liste de données qui contient le coût en temps [T] de tous les joueurs pour nettoyer un labyrinthe avec le niveau [L] dans un jeu. Supposons que nous devons classer les joueurs selon la vitesse à laquelle ils nettoient le labyrinthe. Cependant, une règle supplémentaire s'applique: les joueurs qui nettoient le labyrinthe avec un niveau supérieur ont toujours un rang plus élevé, peu importe la durée du coût.

Bien sûr, vous pouvez essayer de mapper la valeur appariée [T, L] à un nombre réel [R] avec un algorithme qui suit les règles, puis classer tous les joueurs avec la valeur [R].

Cependant, si un tri stable est possible, vous pouvez simplement trier la liste entière par [T] (joueurs plus rapides en premier) puis par [L]. Dans ce cas, l'ordre relatif des joueurs (par coût en temps) ne sera pas modifié après les avoir regroupés par niveau de labyrinthe qu'ils ont nettoyé.

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

Le tri stable retournera toujours la même solution (permutation) sur la même entrée.

Par exemple, [2,1,2] sera trié en utilisant le tri stable comme permutation [2,1,3] (d'abord l'index 2, puis l'index 1 puis l'index 3 dans la sortie triée) Cela signifie que la sortie est toujours mélangée de la même manière. L'autre permutation non stable, mais toujours correcte est [2,3,1].

Le tri rapide n'est pas un tri stable et les différences de permutation entre les mêmes éléments dépendent de l'algorithme de sélection du pivot. Certaines implémentations prennent au hasard et cela peut faire un tri rapide produisant différentes permutations sur la même entrée en utilisant le même algorithme.

Un algorithme de tri stable est déterministe nécessaire.

Quelques autres exemples de la raison de vouloir des tris stables. Les bases de données sont un exemple courant. Prenons le cas d'une base de données de transaction comprenant le nom, le prénom, la date et l'heure d'achat, le numéro d'article et le prix. Supposons que la base de données soit normalement triée par date | heure. Ensuite, une requête est effectuée pour faire une copie triée de la base de données par nom | prénom, puisqu'un tri stable préserve l'ordre d'origine, même si la comparaison de l'enquête n'implique que le nom | prénom, les transactions pour chaque nom | être dans les données | ordre de temps.

Un exemple similaire est Excel classique, qui limitait les tris à 3 colonnes à la fois. Pour trier 6 colonnes, un tri est effectué avec les 3 colonnes les moins significatives, suivi d'un tri avec les 3 colonnes les plus significatives.

Un exemple classique de tri Radix stable est un trieur de cartes, utilisé pour trier par un champ de colonnes numériques de base 10. Les cartes sont triées du chiffre le moins significatif au chiffre le plus significatif. A chaque passage, un jeu de cartes est lu et séparé en 10 cases différentes selon le chiffre de cette colonne. Ensuite, les 10 bacs de cartes sont replacés dans la trémie d'entrée dans l'ordre ("0" en premier, "9" en dernier). Ensuite, un autre passage est effectué par la colonne suivante, jusqu'à ce que toutes les colonnes soient triées. Les trieurs de cartes réels ont plus de 10 bacs car il y a 12 zones sur une carte, une colonne peut être vierge et il y a un bac mal lu. Pour trier les lettres, 2 passes par colonne sont nécessaires, 1ère passe pour le chiffre, 2ème passe pour la zone 12 11.

Plus tard (1937), il y avait des machines d'assemblage (fusion) de cartes qui pouvaient fusionner deux jeux de cartes en comparant les champs. L'entrée était deux jeux de cartes déjà triés, un jeu de cartes maître et un jeu de mise à jour. Le collateur a fusionné les deux ponts en un nouveau bac de collecte et un bac d'archivage, qui étaient éventuellement utilisés pour les doublons principaux afin que le nouveau bac principal ne dispose de cartes de mise à jour qu'en cas de doublons. C'était probablement la base de l'idée derrière le tri de fusion d'origine (ascendant).