Sortiertechniken
****************

Python-Listen haben eine integrierte Methode "list.sort()", die die
Liste an ihrem Platz verändert. Es gibt außerdem die integrierte
Funktion "sorted()", die aus einem iterierbaren Objekt eine neue
sortierte Liste baut.

In diesem Dokument betrachten wir die verschiedenen Techniken, mit
denen sich Daten in Python sortieren lassen.


Grundlagen des Sortierens
=========================

Einfach aufsteigend zu sortieren ist sehr leicht: Rufe einfach die
Funktion "sorted()" auf. Sie gibt eine neue sortierte Liste zurück:

   >>> sorted([5, 2, 3, 1, 4])
   [1, 2, 3, 4, 5]

Du kannst auch die Methode "list.sort()" verwenden. Sie verändert die
Liste an ihrem Platz (und gibt "None" zurück, um Verwirrung zu
vermeiden). Üblicherweise ist sie weniger bequem als "sorted()" – wenn
du die ursprüngliche Liste aber nicht mehr brauchst, ist sie etwas
effizienter.

   >>> a = [5, 2, 3, 1, 4]
   >>> a.sort()
   >>> a
   [1, 2, 3, 4, 5]

Ein weiterer Unterschied ist, dass die Methode "list.sort()" nur für
Listen definiert ist. Die Funktion "sorted()" nimmt dagegen jedes
iterierbare Objekt an.

   >>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
   [1, 2, 3, 4, 5]


Schlüsselfunktionen
===================

Die Methode "list.sort()" und die Funktionen "sorted()", "min()",
"max()", "heapq.nsmallest()" und "heapq.nlargest()" haben einen
Parameter *key*, mit dem sich eine Funktion (oder ein anderes
aufrufbares Objekt) angeben lässt, die vor den Vergleichen auf jedes
Listenelement angewendet wird.

Hier zum Beispiel ein Zeichenkettenvergleich ohne Beachtung der Groß-
und Kleinschreibung mit "str.casefold()":

   >>> sorted("This is a test string from Andrew".split(), key=str.casefold)
   ['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

Der Wert des Parameters *key* sollte eine Funktion (oder ein anderes
aufrufbares Objekt) sein, die ein einzelnes Argument nimmt und einen
Schlüssel für die Zwecke des Sortierens zurückgibt. Diese Technik ist
schnell, weil die Schlüsselfunktion für jeden Eingabedatensatz genau
einmal aufgerufen wird.

Ein häufiges Muster ist, zusammengesetzte Objekte anhand einiger ihrer
Indizes als Schlüssel zu sortieren. Zum Beispiel:

   >>> student_tuples = [
   ...     ('john', 'A', 15),
   ...     ('jane', 'B', 12),
   ...     ('dave', 'B', 10),
   ... ]
   >>> sorted(student_tuples, key=lambda student: student[2])   # sort by age
   [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Dieselbe Technik funktioniert für Objekte mit benannten Attributen.
Zum Beispiel:

   >>> class Student:
   ...     def __init__(self, name, grade, age):
   ...         self.name = name
   ...         self.grade = grade
   ...         self.age = age
   ...     def __repr__(self):
   ...         return repr((self.name, self.grade, self.age))

   >>> student_objects = [
   ...     Student('john', 'A', 15),
   ...     Student('jane', 'B', 12),
   ...     Student('dave', 'B', 10),
   ... ]
   >>> sorted(student_objects, key=lambda student: student.age)   # sort by age
   [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Objekte mit benannten Attributen lassen sich mit einer gewöhnlichen
Klasse erzeugen, wie oben gezeigt, oder sie können Instanzen einer
"dataclass" oder eines *benannten Tupels* sein.


Funktionen des operator-Moduls und teilweise Funktionsauswertung
================================================================

Die oben gezeigten Muster für *Schlüsselfunktionen* sind sehr
verbreitet, daher bietet Python Hilfsfunktionen, die
Zugriffsfunktionen einfacher und schneller machen. Das Modul
"operator" enthält "itemgetter()", "attrgetter()" und eine Funktion
"methodcaller()".

Mit diesen Funktionen werden die obigen Beispiele einfacher und
schneller:

   >>> from operator import itemgetter, attrgetter

   >>> sorted(student_tuples, key=itemgetter(2))
   [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

   >>> sorted(student_objects, key=attrgetter('age'))
   [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Die Funktionen des operator-Moduls erlauben mehrere Sortierebenen. Um
zum Beispiel nach *grade* und dann nach *age* zu sortieren:

   >>> sorted(student_tuples, key=itemgetter(1,2))
   [('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

   >>> sorted(student_objects, key=attrgetter('grade', 'age'))
   [('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

Das Modul "functools" bietet ein weiteres hilfreiches Werkzeug, um
Schlüsselfunktionen zu bauen. Die Funktion "partial()" kann die
Stelligkeit einer Funktion mit mehreren Argumenten verringern und sie
damit als Schlüsselfunktion verwendbar machen.

   >>> from functools import partial
   >>> from unicodedata import normalize

   >>> names = 'Zoë Åbjørn Núñez Élana Zeke Abe Nubia Eloise'.split()

   >>> sorted(names, key=partial(normalize, 'NFD'))
   ['Abe', 'Åbjørn', 'Eloise', 'Élana', 'Nubia', 'Núñez', 'Zeke', 'Zoë']

   >>> sorted(names, key=partial(normalize, 'NFC'))
   ['Abe', 'Eloise', 'Nubia', 'Núñez', 'Zeke', 'Zoë', 'Åbjørn', 'Élana']


Aufsteigend und absteigend
==========================

Sowohl "list.sort()" als auch "sorted()" nehmen einen Parameter
*reverse* mit einem booleschen Wert an. Damit wird absteigendes
Sortieren gekennzeichnet. Um zum Beispiel die Studentendaten in
umgekehrter *age*-Reihenfolge zu bekommen:

   >>> sorted(student_tuples, key=itemgetter(2), reverse=True)
   [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

   >>> sorted(student_objects, key=attrgetter('age'), reverse=True)
   [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]


Sortierstabilität und zusammengesetzte Sortierungen
===================================================

Sortierungen sind garantiert stabil. Das heißt, dass die ursprüngliche
Reihenfolge erhalten bleibt, wenn mehrere Datensätze denselben
Schlüssel haben.

   >>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
   >>> sorted(data, key=itemgetter(0))
   [('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

Beachte, wie die beiden Datensätze für *blue* ihre ursprüngliche
Reihenfolge behalten, sodass "('blue', 1)" garantiert vor "('blue',
2)" steht.

Diese wunderbare Eigenschaft erlaubt es dir, zusammengesetzte
Sortierungen in einer Folge von Sortierschritten aufzubauen. Um zum
Beispiel die Studentendaten nach absteigendem *grade* und dann nach
aufsteigendem *age* zu sortieren, sortiere zuerst nach *age* und dann
erneut nach *grade*:

   >>> s = sorted(student_objects, key=attrgetter('age'))     # sort on secondary key
   >>> sorted(s, key=attrgetter('grade'), reverse=True)       # now sort on primary key, descending
   [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Das lässt sich in eine Hüllfunktion abstrahieren, die eine Liste und
Tupel aus Feld und Richtung annimmt, um in mehreren Durchgängen danach
zu sortieren.

   >>> def multisort(xs, specs):
   ...     for key, reverse in reversed(specs):
   ...         xs.sort(key=attrgetter(key), reverse=reverse)
   ...     return xs

   >>> multisort(list(student_objects), (('grade', True), ('age', False)))
   [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

Der in Python verwendete Algorithmus Timsort führt mehrere
Sortierungen effizient aus, weil er jede in einem Datensatz bereits
vorhandene Ordnung ausnutzen kann.


Decorate-Sort-Undecorate
========================

Dieses Idiom heißt nach seinen drei Schritten Decorate-Sort-
Undecorate:

* Zuerst wird die Ausgangsliste mit neuen Werten dekoriert, die die
  Sortierreihenfolge bestimmen.

* Danach wird die dekorierte Liste sortiert.

* Zuletzt werden die Dekorationen entfernt. So entsteht eine Liste,
  die nur die Ausgangswerte in der neuen Reihenfolge enthält.

Um zum Beispiel die Studentendaten mit dem DSU-Ansatz nach *grade* zu
sortieren:

   >>> decorated = [(student.grade, i, student) for i, student in enumerate(student_objects)]
   >>> decorated.sort()
   >>> [student for grade, i, student in decorated]               # undecorate
   [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

Dieses Idiom funktioniert, weil Tupel lexikografisch verglichen
werden: Zuerst werden die ersten Elemente verglichen. Sind sie gleich,
werden die zweiten Elemente verglichen, und so weiter.

Es ist nicht in allen Fällen zwingend nötig, den Index *i* in die
dekorierte Liste aufzunehmen, aber es bringt zwei Vorteile:

* Die Sortierung ist stabil – haben zwei Elemente denselben Schlüssel,
  bleibt ihre Reihenfolge in der sortierten Liste erhalten.

* Die ursprünglichen Elemente müssen nicht vergleichbar sein, weil die
  Reihenfolge der dekorierten Tupel von höchstens den ersten zwei
  Elementen bestimmt wird. So könnte die ursprüngliche Liste zum
  Beispiel komplexe Zahlen enthalten, die sich nicht direkt sortieren
  lassen.

Ein anderer Name für dieses Idiom ist Schwartzian transform, nach
Randal L. Schwartz, der es unter Perl-Programmierern bekannt gemacht
hat.

Da Python beim Sortieren inzwischen Schlüsselfunktionen bietet,
braucht man diese Technik nicht mehr oft.


Vergleichsfunktionen
====================

Anders als Schlüsselfunktionen, die zum Sortieren einen absoluten Wert
zurückgeben, berechnet eine Vergleichsfunktion die relative Ordnung
zweier Eingaben.

Eine Balkenwaage vergleicht zum Beispiel zwei Proben und liefert eine
relative Ordnung: leichter, gleich oder schwerer. Ebenso gibt eine
Vergleichsfunktion wie "cmp(a, b)" einen negativen Wert für „kleiner
als“, null bei gleichen Eingaben oder einen positiven Wert für „größer
als“ zurück.

Vergleichsfunktionen trifft man häufig, wenn man Algorithmen aus
anderen Sprachen überträgt. Außerdem bieten manche Bibliotheken
Vergleichsfunktionen als Teil ihrer API an. "locale.strcoll()" ist zum
Beispiel eine Vergleichsfunktion.

Für diese Fälle bietet Python "functools.cmp_to_key", um die
Vergleichsfunktion so zu umhüllen, dass sie als Schlüsselfunktion
verwendbar wird:

   sorted(words, key=cmp_to_key(strcoll))  # locale-aware sort order


Strategien für nicht ordenbare Typen und Werte
==============================================

Beim Sortieren kann es zu einer Reihe von Typ- und Wertproblemen
kommen. Hier einige Strategien, die helfen können:

* Wandle nicht vergleichbare Eingabetypen vor dem Sortieren in
  Zeichenketten um:

   >>> data = ['twelve', '11', 10]
   >>> sorted(map(str, data))
   ['10', '11', 'twelve']

Das ist nötig, weil die meisten Vergleiche über Typgrenzen hinweg
einen "TypeError" auslösen.

* Entferne besondere Werte vor dem Sortieren:

   >>> from math import isnan
   >>> from itertools import filterfalse
   >>> data = [3.3, float('nan'), 1.1, 2.2]
   >>> sorted(filterfalse(isnan, data))
   [1.1, 2.2, 3.3]

Das ist nötig, weil der IEEE-754-Standard festlegt: „Every NaN shall
compare unordered with everything, including itself.“

Ebenso lässt sich "None" aus Datensätzen entfernen:

   >>> data = [3.3, None, 1.1, 2.2]
   >>> sorted(x for x in data if x is not None)
   [1.1, 2.2, 3.3]

Das ist nötig, weil "None" nicht mit anderen Typen vergleichbar ist.

* Wandle Abbildungstypen vor dem Sortieren in sortierte Elementlisten
  um:

   >>> data = [{'a': 1}, {'b': 2}]
   >>> sorted(data, key=lambda d: sorted(d.items()))
   [{'a': 1}, {'b': 2}]

Das ist nötig, weil Vergleiche zwischen Dicts einen "TypeError"
auslösen.

* Wandle Mengentypen vor dem Sortieren in sortierte Listen um:

   >>> data = [{'a', 'b', 'c'}, {'b', 'c', 'd'}]
   >>> sorted(map(sorted, data))
   [['a', 'b', 'c'], ['b', 'c', 'd']]

Das ist nötig, weil die in Mengentypen enthaltenen Elemente keine
festgelegte Reihenfolge haben. So kann "list({'a', 'b'})" zum Beispiel
entweder "['a', 'b']" oder "['b', 'a']" ergeben.


Verschiedenes
=============

* Für ein Sortieren, das das Gebietsschema beachtet, verwende
  "locale.strxfrm()" als Schlüsselfunktion oder "locale.strcoll()" als
  Vergleichsfunktion. Das ist nötig, weil „alphabetische“
  Sortierreihenfolgen sich zwischen Kulturen unterscheiden können,
  selbst wenn das zugrunde liegende Alphabet dasselbe ist.

* Der Parameter *reverse* erhält die Sortierstabilität (sodass
  Datensätze mit gleichen Schlüsseln ihre ursprüngliche Reihenfolge
  behalten). Interessanterweise lässt sich dieser Effekt auch ohne den
  Parameter nachbilden, indem man die integrierte Funktion
  "reversed()" zweimal verwendet:

     >>> data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
     >>> standard_way = sorted(data, key=itemgetter(0), reverse=True)
     >>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter(0))))
     >>> assert standard_way == double_reversed
     >>> standard_way
     [('red', 1), ('red', 2), ('blue', 1), ('blue', 2)]

* Die Sortierroutinen verwenden beim Vergleich zweier Objekte "<".
  Eine Standard-Sortierreihenfolge lässt sich einer Klasse daher
  leicht hinzufügen, indem man eine Methode "__lt__()" definiert:

     >>> Student.__lt__ = lambda self, other: self.age < other.age
     >>> sorted(student_objects)
     [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

  Beachte aber, dass "<" auf "__gt__()" zurückfallen kann, wenn
  "__lt__()" nicht implementiert ist (Einzelheiten zur Mechanik stehen
  bei "object.__lt__()"). Um Überraschungen zu vermeiden, empfiehlt
  **PEP 8**, alle sechs Vergleichsmethoden zu implementieren. Der
  Decorator "@~functools.total_ordering" ist dafür da, diese Aufgabe
  zu erleichtern.

* Schlüsselfunktionen müssen nicht unmittelbar von den sortierten
  Objekten abhängen. Eine Schlüsselfunktion kann auch auf äußere
  Quellen zugreifen. Sind die Noten der Studenten zum Beispiel in
  einem Wörterbuch gespeichert, lassen sie sich verwenden, um eine
  separate Liste von Studentennamen zu sortieren:

     >>> students = ['dave', 'john', 'jane']
     >>> newgrades = {'john': 'F', 'jane':'A', 'dave': 'C'}
     >>> sorted(students, key=newgrades.__getitem__)
     ['jane', 'dave', 'john']


Teilweises Sortieren
====================

Manche Anwendungen brauchen nur einen Teil der Daten geordnet. Die
Standardbibliothek bietet mehrere Werkzeuge, die weniger Arbeit
leisten als eine vollständige Sortierung:

* "min()" und "max()" geben den kleinsten beziehungsweise den größten
  Wert zurück. Diese Funktionen gehen die Eingabedaten in einem
  einzigen Durchgang durch und brauchen so gut wie keinen
  Hilfsspeicher.

* "heapq.nsmallest()" und "heapq.nlargest()" geben die *n* kleinsten
  beziehungsweise die *n* größten Werte zurück. Diese Funktionen gehen
  die Daten in einem einzigen Durchgang durch und halten dabei immer
  nur *n* Elemente im Speicher. Für Werte von *n*, die im Verhältnis
  zur Anzahl der Eingaben klein sind, führen diese Funktionen weit
  weniger Vergleiche durch als eine vollständige Sortierung.

* "heapq.heappush()" und "heapq.heappop()" erzeugen und pflegen eine
  teilweise sortierte Anordnung der Daten, die das kleinste Element an
  Position "0" hält. Diese Funktionen eignen sich dafür,
  Prioritätswarteschlangen umzusetzen, wie sie häufig für die
  Ablaufplanung von Aufgaben verwendet werden.
