La fonction sorted() de Python est-elle garantie stable ?

Question

En la documentation ne le garantit pas. Y a-t-il un autre endroit où cela est documenté ?

Je suppose qu'il pourrait être stable puisque la méthode de tri sur les listes est stabilité garantie (Notes 9ème point : "A partir de Python 2.3, la méthode sort() est garantie stable"), et sorted est fonctionnellement similaire. Cependant, je ne suis pas en mesure de trouver une source définitive qui l'affirme.

But : J'ai besoin de trier sur la base d'une clé primaire et aussi d'une clé secondaire dans les cas où la clé primaire est égale dans les deux enregistrements. Si sorted() est garanti stable, je peux trier sur la clé secondaire, puis sur la clé primaire et obtenir le résultat dont j'ai besoin.

PS : Pour éviter toute confusion, j'utilise stable dans le sens de "un tri est stable s'il garantit de ne pas changer l'ordre relatif des éléments qui se comparent".

Answer 1

Oui, l'intention du manuel est bien de garantir que sorted est stable et qu'il utilise exactement le même algorithme que celui de la sort méthode. Je me rends compte que la documentation n'est pas claire à 100 % sur cette identité ; les correctifs de la documentation sont toujours acceptés avec plaisir !

Answer 2

Ils sont stable .

D'ailleurs, il est parfois possible de ne pas savoir si sort et sorted sont stables, en combinant un tri en plusieurs passes avec un tri en une seule passe.

Par exemple, si vous souhaitez trier les objets en fonction de leur last_name , first_name Les attributs, vous pouvez le faire en une seule fois :

sorted_list= sorted(
    your_sequence_of_items,
    key= lambda item: (item.last_name, item.first_name))

en tirant parti de la comparaison de n-uplets.

Cette réponse, telle quelle, couvre la question initiale. Pour d'autres questions relatives au tri, il y a le site Comment trier en Python .

Answer 3

La documentation a été modifiée entre-temps ( Engagement correspondant ) et la documentation actuelle de sorted le garantit explicitement :

Le système intégré sorted() est garantie stable. Un tri est stable s'il garantit de ne pas modifier l'ordre relatif des éléments qui se comparent - ce qui est utile pour les tris en plusieurs passages (par exemple, tri par département, puis par niveau de salaire).

Cette partie de la documentation a été ajoutée à Python 2.7 et Python 3.4(+). conforme la mise en œuvre de cette version linguistique devrait avoir une stabilité sorted .

Notez que pour CPython, l'option list.sort est stable depuis Python 2.3

• Tim Peters a réécrit son list.sort() Cette fois-ci, il s'agit d'un "tri stable" (les entrées égales apparaissent dans le même ordre dans la sortie) et plus rapide qu'auparavant.

Je ne suis pas sûr à 100 % de ce qu'il en est sorted Aujourd'hui, il est simple d'utilisation list.sort mais je n'ai pas vérifié l'historique. Mais il est probable qu'il a "toujours" utilisé list.sort .

Answer 4

La documentation de Python 3.6 sur le tri indique maintenant que

La stabilité des tris est garantie

De plus, dans ce document, il y a un lien vers l'écurie Timsort qui stipule que

Timsort est l'algorithme de tri standard de Python depuis la version 2.3.

Answer 5

En Documentation "What's New" pour Python 2.4 Il est vrai que sorted() crée d'abord une liste, puis appelle sort() sur cette liste, ce qui vous donne la garantie dont vous avez besoin, bien qu'elle ne figure pas dans la documentation "officielle". Vous pouvez également consulter les sources, si vous êtes vraiment inquiet.