Was du hier lernst
- Rekursion
- Teile und herrsche
- List Comprehensions
- Pivotelement
- Seiteneffekte von pop()
- async und await für Animationen
Die Erklärung stammt – leicht überarbeitet für Python 3 – aus dem Buch „Coding for Fun mit Python“ von Lars Heppert, Vorwort.
Warum eigentlich Python?
Python ist eine sehr interessante Sprache mit viel Potenzial für die verschiedensten Einsatzbereiche. Genau deshalb – und weil sich Python-Code sehr leicht lesen lässt – ist sie für ein Buch, in dem es vor allem um den Spaß am Programmieren geht, eine ausgezeichnete Wahl. Genau genommen ist sie die ideale Sprache, um schnell Probleme zu lösen und Dinge einfach einmal auszuprobieren, ohne viel Arbeit investieren zu müssen.
Denn gerade der sonst recht hohe Aufwand beim Programmieren schreckt viele ab und lässt sie zu Standardsoftware greifen. Der Haken dabei ist die Bevormundung: Möglich ist dann eben nur, was der Hersteller vorgesehen hat. Der Erfinder von Python hat das in einem schönen Zitat auf den Punkt gebracht:
»However, while many people nowadays use a computer, few of them are computer programmers. Non-programmers aren't really empowered in how they can use their computer: they are confined to using applications in ways that programmers have determined for them. One doesn't need to be a visionary to see the limitations here.« – Guido van Rossum
Wer nicht programmieren kann, darf seinen Computer also nur so benutzen, wie Programmierer es für ihn vorgesehen haben. Guido van Rossum hat dagegen eine leichte und hochproduktive Sprache gesetzt. Als das Buch erschien, war Python 3.1 gerade ganz frisch – heute ist Python 3 längst Standard, und die Beispiele auf dieser Seite laufen mit Python 3.14 direkt in deinem Browser.
Auch mit jeder neuen Version wird weiter an der Klarheit der Sprache gefeilt. Dieses Ziel ist sehr schön im »Zen of Python« von Tim Peters festgehalten, der im Vorwort des Buchs vollständig abgedruckt ist. Ein paar Kostproben:
Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Readability counts.
If the implementation is easy to explain, it may be a good idea.
Alle neunzehn Sätze bekommst du übrigens mit einer einzigen Zeile Python – probier unten unter »Probier mal« den »Zen of Python« aus.
Quicksort in sieben Zeilen
Ein Beispiel aus der Praxis, das die Einfachheit der Sprache nicht besser ausdrücken könnte, ist die folgende Implementierung des Quicksort-Algorithmus – die einfachste, die ich kenne:
def quicksort(liste):
if len(liste) <= 1:
return liste
pivotelement = liste.pop()
links = [element for element in liste if element < pivotelement]
rechts = [element for element in liste if element >= pivotelement]
return quicksort(links) + [pivotelement] + quicksort(rechts)
Der Algorithmus basiert auf einem einfachen und altbekannten Prinzip: Divide et impera – zu Deutsch: »Teile und herrsche«. Die eigentliche Aufgabe, eine Liste von vergleichbaren Elementen zu sortieren, wird in mehrere Teilschritte zerlegt.
- Ein Teilschritt wählt ein beliebiges Element, das daraufhin als »Mitte« gilt – das Pivotelement. Hier ist es einfach das letzte Element der Liste, das
liste.pop()herausnimmt. - Ausgehend von dieser Mitte werden die kleineren Elemente in die Liste
linksund die größeren oder gleichen in die Listerechtssortiert. Das erledigen zwei List Comprehensions – Listen, die sich fast wie ein Satz lesen: »jedes Element aus der Liste, falls es kleiner ist als das Pivotelement«. - Zu guter Letzt wird derselbe Schritt per Rekursion für die beiden Listen
linksundrechtserneut ausgeführt, und die Ergebnisse werden mit dem Pivotelement in der Mitte zusammengesetzt.
Die Rekursion endet erst, wenn die Teillisten nur noch ein Element enthalten (oder gar keins). Denn eine Liste mit genau einem Element ist – wie der Informatiker sagen würde – immer sortiert.
Ein Durchlauf von Hand
Wie das im Einzelnen abläuft, siehst du am besten an einer kleinen Liste. Nehmen wir [3, 7, 1, 9, 4]:
| Aufruf | Pivotelement | links | rechts |
|---|---|---|---|
quicksort([3, 7, 1, 9, 4]) |
4 | [3, 1] |
[7, 9] |
quicksort([3, 1]) |
1 | [] |
[3] |
quicksort([7, 9]) |
9 | [7] |
[] |
Die kleinen Listen [], [3] und [7] kommen sofort unverändert zurück. Dann setzt jeder Aufruf sein Ergebnis zusammen: [] + [1] + [3] ergibt [1, 3], [7] + [9] + [] ergibt [7, 9], und ganz oben entsteht [1, 3] + [4] + [7, 9] – also [1, 3, 4, 7, 9].
Beachte: Das Pivotelement steht nach dem Teilen schon an seinem endgültigen Platz. Links davon ist alles kleiner, rechts davon alles größer oder gleich – egal, wie die beiden Hälften später sortiert werden.
Was die Animation zeigt
Das Programm oben besteht aus zwei Teilen. Teil 1 ruft die Funktion aus dem Buch auf und schreibt das Ergebnis in die Konsole. Teil 2 sortiert 32 Balken mit einem Zwilling der Funktion, quicksort_animiert, der Schritt für Schritt zeichnet, was passiert:
- Gelb ist das Pivotelement des aktuellen Aufrufs.
- Blau ist der Abschnitt, den dieser Aufruf gerade sortiert. Nach dem Teilen färbt er sich türkis (kleiner) und lila (größer oder gleich).
- Grün sind Balken, die schon an ihrem endgültigen Platz stehen.
- Die Klammern unter den Balken sind die laufenden Aufrufe – jeder rekursive Aufruf legt eine neue, kürzere Klammer unter die seines Aufrufers. Das ist der Aufrufstapel, den Python sich merkt, um nach jedem Aufruf wieder dorthin zurückzukehren, wo es herkam.
Der Zwilling macht dasselbe wie das Original, mit zwei Unterschieden. Er schreibt nach dem Teilen links + [pivotelement] + rechts zurück in die Balkenliste, damit du den Zwischenstand siehst. Und er ist mit async def definiert und wartet mit await zeige(...) nach jedem Schritt. So bekommt der Browser Zeit, das Bild zu zeichnen. Auch die rekursiven Aufrufe brauchen deshalb ein await – ansonsten ist die Struktur Zeile für Zeile die aus dem Buch.
Genau hingeschaut
Sieben Zeilen, die sich lesen wie eine Erklärung des Verfahrens – kürzer geht es kaum. Wer genau hinsieht, entdeckt trotzdem ein paar Stellen, an denen die Eleganz ihren Preis hat. Gut so: Genau darum geht es beim Lernen.
pop() verändert die übergebene Liste. liste.pop() nimmt das Pivotelement aus genau der Liste heraus, die du der Funktion gegeben hast. Rufst du quicksort(zahlen) auf, fehlt zahlen danach das letzte Element. Deshalb übergibt das Programm mit list(zahlen) eine Kopie. Die rekursiven Aufrufe sind davon nicht betroffen – links und rechts sind ohnehin neue Listen.
Jedes Element wird zweimal verglichen. Die beiden List Comprehensions laufen jeweils einmal durch die ganze Liste. Eine einzige Schleife, die jedes Element entweder links oder rechts einsortiert, wäre doppelt so sparsam – aber weniger schön zu lesen. Und »Readability counts«.
Vorsortierte Listen sind der schlimmste Fall. Weil immer das letzte Element das Pivotelement ist, trifft es bei einer schon sortierten Liste stets das größte. Dann landet alles links, und jeder Aufruf wird nur ein einziges Element los. Statt etwa log₂(n) Ebenen tief – bei 32 Zahlen etwa fünf, in der Praxis meist sieben bis neun – geht die Rekursion n Ebenen tief, und die Zahl der Vergleiche wächst quadratisch mit der Länge der Liste. Bei ein paar Tausend vorsortierten Zahlen gibt Python sogar ganz auf: Nach 1000 verschachtelten Aufrufen meldet es einen RecursionError. Die Abhilfe ist verblüffend einfach, du findest sie unter »Probier mal«.
Im Alltag schreibst du natürlich keinen eigenen Sortieralgorithmus, sondern nimmst sorted(liste) oder liste.sort(). Dahinter steckt Timsort, ein Verfahren, das Tim Peters 2002 eigens für Python entwickelt hat – derselbe Tim Peters, von dem der Zen of Python stammt.
Direkt ans Eingemachte
Wie du siehst, geht es in diesem Buch immer direkt ans Eingemachte, so dass du dich nicht mit trockener Theorie abfinden musst. Alles wird direkt ausprobiert und programmiert, mit viel Freiraum für deine eigene Kreativität. Hin und wieder führt das auch zu Code, der noch ein wenig Aufräumarbeit verkraften kann – dafür kommen wir schneller ans Ziel und sparen uns trockene Passagen. Zwischendrin gibt es immer wieder Hinweise auf mögliche Fallgruben und Optimierungen, die du jederzeit selbst umsetzen kannst.
Damals gab es zum Buch eine eigene Website unter coding.heppert.com. Heute findest du die Beispiele hier – lauffähig, ohne Installation, zum Verändern und Ausprobieren. Viel Spaß dabei!
Probier mal
Jede Variante ändert den Code oben. Ein Klick auf »Ausprobieren« übernimmt die Änderung in den Editor und startet das Programm. »Zurücksetzen« holt das Original zurück.
-
01Der schlimmste Fall: schon sortiert
Gib Quicksort eine Liste, die schon sortiert ist. Das letzte Element ist dann immer das größte, alle anderen landen links, rechts bleibt leer. Jeder Aufruf knabbert nur ein einziges Element ab – die Klammern unten stapeln sich zu einer Treppe, 31 Ebenen tief. Bei gemischten Zahlen sind es meist nur sieben bis neun. Aus »teile und herrsche« wird »schäle und warte«.
- balken = random.sample(range(1, ANZAHL + 1), ANZAHL) + balken = list(range(1, ANZAHL + 1)) # schon sortiert! - TEMPO = 0.5 + TEMPO = 0.25 -
02Mit Zufall gegen den schlimmsten Fall
Dieselbe sortierte Liste, aber das Pivotelement wird jetzt zufällig gewählt statt immer das letzte. Schon ist der Stapel wieder flach. Genau so machen es viele echte Quicksort-Implementierungen: Ein bisschen Zufall schützt vor bösartig vorsortierten Eingaben.
- balken = random.sample(range(1, ANZAHL + 1), ANZAHL) + balken = list(range(1, ANZAHL + 1)) # schon sortiert! - index = len(liste) - 1 # das letzte Element – wie im Buch + index = random.randrange(len(liste)) # ein zufälliges Element -
03Absteigend sortieren
Die Sortierrichtung steckt allein in den zwei Vergleichen. Dreh sie um, und die Größeren wandern nach links. In der Funktion aus dem Buch funktioniert derselbe Tausch genauso.
- links = [element for element in liste if element < pivotelement] # kleiner + links = [element for element in liste if element > pivotelement] # größer - rechts = [element for element in liste if element >= pivotelement] # größer oder gleich + rechts = [element for element in liste if element <= pivotelement] # kleiner oder gleich - {len(links)} kleiner, {len(rechts)} größer oder gleich + {len(links)} größer, {len(rechts)} kleiner oder gleich -
04Wo ist die letzte Zahl geblieben?
Rufe die Funktion aus dem Buch einmal ohne Kopie auf und schau dir danach die Liste
zahlenan: Ihr fehlt das letzte Element.liste.pop()entfernt das Pivotelement nämlich aus genau der Liste, die du übergeben hast. Deshalb steht im Programmquicksort(list(zahlen)).- print("sortiert: ", quicksort(list(zahlen))) # list(...) übergibt eine Kopie + print("sortiert: ", quicksort(zahlen)) # diesmal ohne Kopie … + print("und zahlen:", zahlen) # … und hier fehlt jetzt etwas -
05Der Zen of Python
Das Vorwort zitiert den »Zen of Python« von Tim Peters – neunzehn Merksätze für guten Python-Code. Du musst sie nicht abtippen: Python hat sie eingebaut. Eine einzige Zeile
import thisschreibt sie in die Konsole.- import random + import this # der Zen of Python + import random
Vom Buch in den Browser
Listing 0.1 aus dem Vorwort läuft unverändert unter Python 3: keine print-Anweisung, keine Ganzzahldivision, nichts, was es nur in Python 2 gab. Die Funktion quicksort im Programm oben ist Zeichen für Zeichen die aus dem Buch.
Neu hinzugekommen ist alles drumherum:
- Teil 1 ruft die Funktion mit zehn Zufallszahlen auf und gibt das Ergebnis aus. Das Buch zeigte nur die Funktion selbst. Der Aufruf
quicksort(list(zahlen))übergibt eine Kopie, damitpop()die Listezahlennicht verändert. - Teil 2 ist ein Zwilling der Funktion für die Animation. Er ist mit
async defdefiniert, weil er nach jedem Schritt mitawait zeige(...)auf das nächste Bild wartet. Im Browser zeichnet die Seite nur, wenn das Programm ihr kurz die Kontrolle zurückgibt. - Der Zwilling nimmt das Pivotelement mit
liste.pop(index)stattliste.pop()heraus. Mitindex = len(liste) - 1ist das genau dasselbe – so lässt sich unter »Probier mal« aber auch ein zufälliges Pivotelement wählen. - Damit die Balken den Zwischenstand zeigen, schreibt der Zwilling nach jedem Teilen
links + [pivotelement] + rechtsan die passende Stelle der Balkenliste zurück. Die Rekursion selbst arbeitet wie im Original mit neuen Listen. - Gezeichnet wird mit c4f, der kleinen Zeichen-API dieser Website:
screen.rectfür die Balken,screen.linefür die Klammern des Aufrufstapels,screen.textfür die Beschriftung.
Auf dem eigenen Rechner brauchst du für die Funktion aus dem Buch gar nichts außer Python. Die Animation würdest du dort zum Beispiel mit pygame zeichnen und das Programm mit asyncio.run(main()) statt await main() starten.
Original aus dem Buch ansehen listing-0-1.py · Python 2
def quicksort(liste):
if len(liste) <= 1:
return liste
pivotelement = liste.pop()
links = [element for element in liste if element < pivotelement]
rechts = [element for element in liste if element >= pivotelement]
return quicksort(links) + [pivotelement] + quicksort(rechts)
