Informationen zur integrierten sort () -Methode von Python

104

Welchen Algorithmus verwendet die sort()in Python integrierte Methode? Ist es möglich, sich den Code für diese Methode anzusehen?

python algorithm sorting python-internals Johannes
quelle
10
Natürlich kann man sich den Code für die Methode ansehen - Python ist ein Open-Source-Projekt. Die Methode ist jedoch wahrscheinlich in C implementiert, sodass Sie etwas über C wissen müssen, um einen Sinn daraus zu ziehen.
Chris Lutz
Ist die Version wichtig?
Meder Omuraliev
@melder: Nein =) Ich möchte mir nur einen Pro-Algorithmus ansehen: P @chris: wie?
Johannes
3
Laden Sie den Quellcode in den Python-Interpreter herunter. Ich weiß nicht, wo sie die sort()Methode implementieren oder wie die Formatierung für den Interpreter ist, aber sie muss irgendwo drin sein, und ich wette, sie ist aus Geschwindigkeitsgründen in C implementiert.
Chris Lutz
Hier ist ein Beispiel für die Verwendung
Hari Ganesan

Antworten:

118

Sicher! Der Code ist hier , beginnend mit der Funktion isltund für eine ganze Weile ;-). Wie Chris 'Kommentar andeutet, handelt es sich um C-Code. Du wirst auch lesen wollen diese Textdatei um eine Texterklärung, Ergebnisse usw. usw. zu erhalten.

Wenn Sie lieber Java-Code als C-Code lesen, können Sie sich Joshua Blochs Implementierung von Timsort in und für Java ansehen (Joshua ist auch derjenige, der 1997 den modifizierten Mergesort implementiert hat, der immer noch in Java verwendet wird, und man kann hoffen, dass Java dies tut schließlich zu seinem jüngsten Hafen von Timsort wechseln).

Eine Erklärung des Java-Ports von timsort finden Sie hier , der Unterschied ist hier (mit Zeigern auf alle benötigten Dateien), die Schlüsseldatei ist hier - FWIW, während ich ein besserer C-Programmierer als Java-Programmierer bin, finde ich in diesem Fall Joshuas Java-Code ist insgesamt besser lesbar als Tims C-Code ;-).

Alex Martelli
quelle
4
@Chris, "Python-Quellen durchsuchen" ist eine Verknüpfung in allen Lesezeichenleisten meines Browsers - sie verweist auf svn.python.org/view/python/trunk ;-) .
Alex Martelli
Ich möchte wissen, was die Funktion list_ass_item()tut. :)
Chris Lutz
2
Führt die Zuweisung zu einem Element der Liste durch (genau wie list_ass_slice die Zuweisung zu einem Slice der Liste durchführt), hat nichts mit Sortieren zu tun. Ich denke, die Abkürzung für "Zuweisung" macht den Namen lustig ...
Alex Martelli
3
Die aktuelle Version von listsort.txtfügt einige Notizen hinzu, die sich mit häufigen Verwirrungen befassen.
Tim Peters
30

Ich wollte nur einen sehr hilfreichen Link liefern, den ich in Alex 'ansonsten umfassender Antwort verpasst habe: Eine allgemeine Erklärung von Pythons Timsort (mit !).

(Ja, der Algorithmus ist jetzt im Grunde als Timsort bekannt. )

u0b34a0f6ae
quelle
9

In frühen Python-Versionen implementierte die Sortierfunktion eine modifizierte Version von Quicksort. Es wurde jedoch als instabil eingestuft und ab 2.3 wurde auf die Verwendung eines adaptiven Mergesort-Algorithmus umgestellt.

Silfverstrom
quelle
quicksort wird nicht als instabil eingestuft - nach den allgemein verwendeten Definitionen ist quicksort instabil - das heißt, die ursprüngliche Reihenfolge von zwei Objekten wird nicht beibehalten, wenn sie während dieser Sortierung gleich sind. Ein instabiler Sortieralgorithmus bedeutet, dass Sie sich alle Arten von "Magie" einfallen lassen müssen, um Daten mit mehreren Kriterien sinnvoll zu sortieren, anstatt einfach Sortieraufrufe verketten zu können - in timsort, wenn Sie nach DOB und dann nach Namen sortieren möchten Sie sortieren einfach zuerst nach Namen und dann nach DOB. Das können Sie mit Quicksort nicht tun
Tony Suffolk 66