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

Question

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

Answer 1

On dit d'un algorithme de tri qu'il est stable si deux objets avec des clés égales apparaissent dans le même ordre dans la sortie triée qu'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 à bulles, etc. Et certains algorithmes de tri ne le sont pas, comme le tri par tas, le tri rapide, etc.

Contexte un algorithme de tri "stable" conserve dans l'ordre les éléments ayant la même clé de tri. 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, nous obtenons un tri stable :

apple
peach
straw
spork

Dans un instable algorithme de tri, straw o spork peuvent être interchangées, mais dans une situation stable, elles restent dans les mêmes positions relatives (c'est-à-dire que, puisque straw apparaît avant spork dans l'entrée, il apparaît également avant spork dans la sortie).

Nous pourrions trier la liste de mots à l'aide de cet algorithme : tri stable par la colonne 5, puis 4, puis 3, puis 2, puis 1. Au final, elle sera correctement triée. Convainquez-vous-en. (au fait, cet algorithme s'appelle le tri radix)

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

Vous ne pouvez pas empiler des sortes instables de la même façon.

Answer 2

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 ne peut pas satisfaire l'affaire. - _{^{Je remercie mon professeur d'algorithmique, Didem Gozupek, qui m'a permis de mieux comprendre les algorithmes.}} .

J'ai à nouveau dû modifier la question en raison de certains commentaires selon lesquels certaines personnes ne saisissent pas la logique de la présentation. Il illustre le tri en fonction des premiers éléments. D'autre part, vous pouvez considérer l'illustration constituée de paires clé-valeur.

Algorithmes de triage stables :

• Tri par insertion
• Fusionner le tri
• Tri à bulles
• Tim Sort
• Triage par comptage
• Tri des blocs
• Quadsort
• Tri de la bibliothèque
• Shaker à cocktail Tri
• Tri des gnomes
• Tri impair-pair

Algorithmes de triage instables :

• Triage en tas
• Tri de sélection
• Tri des coquilles
• Tri rapide
• Introsort (soumis à Quicksort)
• Triage des arbres
• Triage du cycle
• Tronc commun
• Triage par tournoi (sous réserve d'Hesapsort)

Answer 3

La stabilité du tri signifie que les enregistrements ayant 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 et gourmand en mémoire provenant d'une bibliothèque, comme heapsort ou quicksort, et l'oublier.

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

Vous pouvez transformer un algorithme instable en un algorithme stable en ajoutant le numéro de l'enregistrement original comme clé de dernier rang pour chaque enregistrement.

Answer 4

Cela dépend de ce que vous faites.

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

Answer 5

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, 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).