[Python-de] Dictionary sortieren???

Martin v. Löwis martin at v.loewis.de
Thu May 29 13:21:23 EDT 2003


Klaus Meyer <km-news1 at onlinehome.de> writes:

> Leider steht in der Doku nicht, wie Sort funktioniert, wenn die Liste
> nicht trivial ist. Man kann's natürlich durch ausprobieren erforschen,
> aber welchen Wert hat das, kann man sich darauf verlassen, das die
> nächste Python-Version immer noch genauso (undokumentiert) sortiert?

Nun ja. Es gibt die offensichtlichen Fakten und die weniger
offensichtlichen.

Zu den offensichtlichen gehört, dass "offensichtlich" cmp verwendet
wird, wenn keine cmpfunc angegeben ist, siehe

http://www.python.org/doc/current/lib/typesseq-mutable.html

"Offensichtlich" ist ebenfalls, dass das Sortieren beendet wird, wenn
für alle Indizes n gilt: cmpfunc(L[n], L[n+1]) <= 0

Zu den weniger offensichtlichen Fragen gehören diese:

1. Welche Ordnung wird gefunden, wenn es Listenelemente gibt, für
   die cmpfunc(L[n], L[n+1]) == 0? 
   Antwort: Hängt von der Python-Version ab. Wenigstens Python 2.3
   (evtl. auch schon 2.2) sortiert stabil.

2. Welche Komplexität hat der Sortieralgorithmus?
   Antwort: Das ist absichtlich undokumentiert und kann sich von
   Version zu Version ändern.

3. Was passiert, wenn cmpfunc keine vollständige Ordnung auf den
   Elementen definiert?
   Antwort: Undefiniert.

4. Was macht cmp für nicht-numerische Typen?
   Antwort A: Das ist keine Frage zur Semantik von sort.
   Antwort B: Das hängt stark von der Python-Version ab.
     Falls es sich um Klasseninstanzen handelt, die cmp
     nicht überdefinieren, so ist cmp(a,b) == cmp(id(a),id(b))

Ciao,
Martin



More information about the Python-de mailing list