À propos de la méthode sort () intégrée de Python

104

Quel algorithme la sort()méthode intégrée en Python utilise-t-elle? Est-il possible de consulter le code de cette méthode?

python algorithm sorting python-internals Johannes
la source
10
Bien sûr, il est possible de consulter le code de la méthode - Python est un projet open-source. La méthode est probablement implémentée en C, cependant, vous devrez donc en savoir un peu plus sur C pour lui donner un sens.
Chris Lutz
La version est-elle importante?
meder omuraliev
@melder: Non =) Je veux juste jeter un œil à un algorithme pro: P @chris: comment?
Johannes
3
Téléchargez le code source dans l'interpréteur Python. Je ne sais pas où ils implémentent la sort()méthode, ou quel est le formatage de l'interpréteur, mais il doit y avoir quelque part, et je parie que c'est implémenté en C pour des problèmes de vitesse.
Chris Lutz
Voici un exemple d'utilisation
Hari Ganesan

Réponses:

119

Sûr! Le code est là , en commençant par la fonction isltet en continuant pendant un certain temps ;-). Comme le suggère le commentaire de Chris, c'est du code C. Vous voudrez également lire ce fichier texte pour une explication textuelle, les résultats, etc. etc.

Si vous préférez lire du code Java plutôt que du code C, vous pouvez regarder l'implémentation de timsort par Joshua Bloch dans et pour Java (Joshua est également le gars qui a implémenté, en 1997, le mergesort modifié qui est toujours utilisé en Java, et on peut espérer que Java finalement passer à son récent port de timsort).

Une explication du port Java de timsort est ici , le diff est ici (avec des pointeurs vers tous les fichiers nécessaires), le fichier clé est ici - FWIW, alors que je suis un meilleur programmeur C que le programmeur Java, dans ce cas je trouve Le code Java de Joshua est globalement plus lisible que le code C de Tim ;-).

Alex Martelli
la source
4
@Chris, "Parcourir les sources Python" est un raccourci dans toutes les barres de signets de mon navigateur - il pointe vers svn.python.org/view/python/trunk ;-).
Alex Martelli
Je veux savoir ce que fait la fonction list_ass_item(). :)
Chris Lutz
2
Effectue une affectation à un élément de la liste (tout comme list_ass_slice effectue une affectation à une tranche de la liste), rien à voir avec le tri. Je suppose que l'abréviation de «devoir» rend le nom drôle ...
Alex Martelli
3
La version actuelle de listsort.txtajoute quelques notes qui traitent des confusions courantes.
Tim Peters
31

Je voulais juste fournir un lien très utile que j'ai manqué dans la réponse par ailleurs complète d'Alex: Une explication de haut niveau du tri temporel de Python (avec des visualisations graphiques!).

(Oui, l'algorithme est essentiellement connu sous le nom de Timsort maintenant)

u0b34a0f6ae
la source
9

Dans les premières versions de python, la fonction de tri implémentait une version modifiée de quicksort. Cependant, il a été jugé instable et à partir de 2.3, ils sont passés à l'utilisation d'un algorithme de tri de fusion adaptatif.

Silfverstrom
la source
quicksort n'est pas «jugé instable» - selon les définitions couramment utilisées, quicksort est instable - c'est-à-dire que l'ordre original de deux objets n'est pas conservé, s'ils sont égaux pendant ce tri. Avoir un algorithme de tri instable signifie que vous devez trouver toutes sortes de `` magie '' pour trier judicieusement les données avec plusieurs critères, plutôt que de simplement pouvoir enchaîner les appels de tri - dans timsort si vous voulez trier par DOB puis par nom , vous triez simplement par nom d'abord, puis DOB Vous ne pouvez pas faire ça avec quicksort
Tony Suffolk 66