La fonction sorted () de python est-elle garantie pour être stable?

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

Je suppose que cela pourrait être stable puisque la méthode de tri sur les listes est garantie d'être stable (Notes 9e point: "À partir de Python 2.3, la méthode sort () est garantie d'être stable"), et trié est fonctionnellement similaire. Cependant, je ne suis pas en mesure de trouver une source définitive qui le dise.

Objectif: je dois trier en fonction d'une clé primaire et également d'une clé secondaire dans les cas où la clé primaire est égale dans les deux enregistrements. Si sorted () est garanti pour être stable, je peux trier sur la clé secondaire, puis trier 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 égaux".

Oui, l'intention du manuel est en effet de garantir qu'il sortedest stable et en effet qu'il utilise exactement le même algorithme que la sortméthode. Je me rends compte que les documents ne sont pas clairs à 100% sur cette identité; les correctifs doc sont toujours acceptés avec plaisir!

Ils sont stables .

Au fait: vous pouvez parfois ignorer si le tri et le tri sont stables, en combinant un tri multi-passes dans un tri en un seul passage.

Par exemple, si vous voulez trier les objets en fonction de leurs last_name, first_nameattributs, vous pouvez le faire en un seul passage:

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

tirant parti de la comparaison de tuple.

Cette réponse, telle quelle, couvre la question initiale. Pour d'autres questions liées au tri, il y a le guide de tri Python .

La documentation a changé entre-temps ( commit pertinent ) et la documentation actuelle de sortedle garantit explicitement:

La sorted()fonction intégrée est garantie pour être stable. Un tri est stable s'il garantit de ne pas changer l'ordre relatif des éléments qui se comparent égaux - cela est utile pour le tri en plusieurs passes (par exemple, trier par département, puis par classe de salaire).

Cette partie de la documentation a été ajoutée à Python 2.7 et Python 3.4 (+), donc toute implémentation conforme de cette version du langage doit avoir un fichier stable sorted.

Notez que pour CPython, le list.sortest stable depuis Python 2.3

• Tim Peters a réécrit son list.sort()implémentation - celle-ci est un "tri stable" (les entrées égales apparaissent dans le même ordre dans la sortie) et plus rapide qu'avant.

Je ne suis pas sûr à 100% sorted, de nos jours, c'est simple list.sort, mais je n'ai pas vérifié l'historique pour cela. Mais il est probable qu'il soit «toujours» utilisé list.sort.

Les documents "What's New" pour Python 2.4 font effectivement le point que sorted () crée d'abord une liste, puis appelle sort () dessus, vous fournissant la garantie dont vous avez besoin mais pas dans la documentation "officielle". Vous pouvez également simplement vérifier la source, si vous êtes vraiment inquiet.

La documentation Python 3.6 sur le tri indique maintenant que

Les tris sont garantis stables

En outre, dans ce document, il y a un lien vers l'écurie Timsort , qui indique que

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