Sortieren

Du suchst die Nummer von jemandem, dessen Name mit S anfängt. Du nimmst dein Telefon, wischst einmal, und drei Sekunden später steht der Kontakt vor dir. In deinem Adressbuch stehen ein paar hundert Namen — angesehen hast du vielleicht zehn davon.

Das geht nur aus einem Grund: Die Namen stehen alphabetisch. Stünden sie in der Reihenfolge, in der du sie angelegt hast — die Nummer von vor vier Jahren ganz oben, der Kontakt von gestern ganz unten —, bliebe dir nichts übrig, als von oben nach unten jeden einzelnen anzusehen, bis der richtige kommt. Bei dreihundert Kontakten sind das im Mittel hundertfünfzig.

Geordnet hat diese Namen niemand von Hand. Dein Telefon tut es, jedes Mal, wenn ein Kontakt dazukommt. Und es tut es, weil sich die Arbeit auszahlt: einmal ordnen, danach beliebig oft schnell finden.

Buchstaben sind Zahlen

Namen zu ordnen und Zahlen zu ordnen ist dieselbe Aufgabe. Ein Rechner legt Buchstaben nämlich ohnehin als Zahlen ab — jedem Zeichen ist eine Nummer zugeordnet, und ord() verrät sie:

print(ord("A"))
print(ord("B"))

A ist 65, B ist 66. Deshalb weiß dein Telefon, dass „Berg" vor „Meier" gehört: Es vergleicht keine Buchstaben, es vergleicht Zahlen. Für den Rest dieses Kapitels nehmen wir deshalb gleich Zahlen — man sieht ihnen die Ordnung an, ohne nachzuschlagen.

Ordne selbst

Bevor du ein Sortierverfahren des Rechners ansiehst, ordnest du selbst. Auf dem Tisch unten liegen sieben Karten auf festen Plätzen, und alle Plätze sind belegt. Abseits der Reihe liegt ein einziger freier Platz — mehr Platz hast du nicht. Jeder Tausch kostet dich deshalb drei Züge: parken, umsetzen, zurückholen. Den Handgriff hast du im Listen-Kapitel kennengelernt.

Ordne die Karten aufsteigend — die kleinste Zahl nach links.

1

2

3

4

5

6

7

Merker

Der einzige freie Platz — und er fasst genau eine Karte. In der Reihe selbst ist zu Beginn nichts frei.

Wähle eine Karte und dann einen freien Platz — ziehen geht auch.

Umlegungen: 0

Sieben Karten, ein freier Platz

1. Ordne die Reihe aufsteigend — die kleinste Zahl ganz links, die größte ganz rechts. Es gibt hier keinen falschen Weg.
2. Lies ab, wie viele Umlegungen du gebraucht hast, und schreib die Zahl auf.
3. Beschreib in zwei bis drei Sätzen, wie du dabei vorgegangen bist — so genau, dass jemand anderes es nachmachen könnte. Heb den Zettel auf, du brauchst ihn am Ende des Kapitels noch einmal.

Fünf Zahlen, drei Wege

Du bist eben nach Gefühl vorgegangen. Ein Rechner hat kein Gefühl. Er braucht eine Vorschrift, die bei jeder Reihe funktioniert und bei der an jeder Stelle feststeht, was als Nächstes zu tun ist. Es gibt Dutzende solcher Vorschriften, und sie unterscheiden sich nicht darin, ob sie funktionieren — sie tun es alle —, sondern darin, wie sie vorgehen und wie viel Arbeit das macht.

Wie unterschiedlich die vorgehen, hat die Sapientia-Universität in Rumänien im YouTube-Kanal AlgoRythmics tanzend sichtbar gemacht: Jede:r Tänzer:in ist eine Zahl, jeder Vergleich ein Blickwechsel, jeder Tausch ein Platzwechsel. Wenn du magst, kannst du dir dies hier ansehen:

• Bubble-Sort als ungarischer Csángó-Tanz
• Insertion-Sort als rumänischer Volkstanz
• Selection-Sort als Volkstanz der Roma
• Quick-Sort als ungarischer Burschentanz

Sehen wir uns dasselbe noch einmal an, diesmal mit Zahlen und mit Python. Drei Verfahren nehmen wir uns dafür vor. Fünf Zahlen reichen völlig; bei mehr verlierst du beim Zusehen den Überblick. Nimm diese:

5, 2, 4, 1, 3

Jede Animation zählt zwei Dinge mit. Die Tausche — das ist das, was dich am Tisch je drei Züge gekostet hat. Und die Vergleiche — jedes Mal, wenn zwei Zahlen nebeneinandergehalten werden und die Frage lautet, welche die kleinere ist.

Im Dreierteam

Jede Person übernimmt eines der drei Verfahren aus den nächsten Abschnitten: Bubble-Sort, Insertion-Sort oder Selection-Sort.

1. Klick dich in deiner Animation Schritt für Schritt durch, bis du das Verfahren jemandem erklären kannst.
2. Sortiere die fünf Zahlen zusätzlich von Hand auf Papier. Schreib nach jeder Veränderung die ganze Reihe neu auf.
3. Erklärt euch die drei Verfahren gegenseitig. Am Ende hat jede Person alle drei auf dem Papier stehen.
4. Tragt zusammen, wie viele Vergleiche und wie viele Tausche jedes Verfahren gebraucht hat. Die Animation zählt für euch mit.

Bubble-Sort: Nachbarn tauschen

bleeptrack erklärt Bubble-Sort — Video bei YouTube ansehen

Das erste Verfahren schaut immer nur auf zwei Zahlen, die nebeneinanderliegen. Ist die linke größer, werden die beiden getauscht. Dann rückt der Blick ein Feld weiter.

Bubble-Sort mit 5 Zahlen

5

2

4

1

3

Los geht es.

Vergleiche: 0   Tausche: 0

Zahlen: 5Tempo: langsam

Läufst du damit einmal durch die ganze Liste, ist sie noch nicht sortiert — aber die größte Zahl ist mit Sicherheit ganz hinten angekommen. Sie ist durchgereicht worden wie eine Luftblase, die aufsteigt. Daher der Name.

Also läufst du wieder durch. Und wieder. Bis bei einem Durchgang kein einziges Mal mehr getauscht werden musste. Genau das ist die Abbruchbedingung — und dafür brauchst du eine Variable, die sich merkt, ob in diesem Durchgang etwas passiert ist.

Eine Sache brauchst du dafür neu. Bisher bist du mit for sorte in sorten: über die Werte einer Liste gelaufen. Hier reicht das nicht: Du willst zwei Nachbarn vergleichen und danach vertauschen, und dafür brauchst du ihre Plätze. Zählschleife und len() zusammen geben dir die:

for i in range(len(zahlen)):
    print(zahlen[i])

i ist der Index, zahlen[i] das Element an dieser Stelle. Wo du zwei Nachbarn brauchst, sind das zahlen[i] und zahlen[i + 1] — und dann musst du dir überlegen, wie weit i überhaupt laufen darf, damit es den zweiten davon noch gibt.

Den Tausch selbst hast du im Listen-Kapitel gebaut.

Aufgabe

Vergleiche die Zahl der Tausche am Ende mit der, die ihr im Team von Hand herausbekommen habt.

Insertion-Sort: an die richtige Stelle bringen

bleeptrack erklärt Insertion-Sort — Video bei YouTube ansehen

Das zweite Verfahren behandelt die Liste, als bestünde sie aus zwei Teilen. Links ist alles schon geordnet, rechts liegt der Rest. Am Anfang ist der geordnete Teil nur die erste Zahl lang — eine einzelne Zahl ist immer geordnet.

Dann kommt die nächste Zahl an die Reihe. Sie wandert so weit nach links, bis links von ihr nichts Größeres mehr steht. Genau dort bleibt sie liegen, und der geordnete Teil ist um eins gewachsen.

Insertion-Sort mit 5 Zahlen

5

2

4

1

3

Los geht es.

Vergleiche: 0   Tausche: 0

Zahlen: 5Tempo: langsam

Weil jede Zahl an ihrer Stelle eingefügt wird, heißt das Verfahren Insertion-Sort, nach dem englischen Wort für Einfügen.

zahlen = [5, 2, 4, 1, 3]

for i in range(1, len(zahlen)):
    j = i
    while j > 0 and zahlen[j - 1] > zahlen[j]:
        zahlen[j - 1], zahlen[j] = zahlen[j], zahlen[j - 1]
        j = j - 1

print(zahlen)

Die äußere Schleife beginnt bei 1, nicht bei 0: Die erste Zahl ist ja schon geordnet. Die innere Schleife lässt die Zahl nach links wandern und hört bei der ersten der beiden Bedingungen auf, die nicht mehr stimmt — entweder ist links nichts Größeres mehr, oder es ist überhaupt nichts mehr links.

Selection-Sort: erst suchen, dann setzen

bleeptrack erklärt Selection-Sort — Video bei YouTube ansehen

Das dritte Verfahren dreht die Sache um. Es tauscht nicht dort, wo es gerade nötig ist, sondern sucht erst und setzt dann: Es geht die ganze noch ungeordnete Rest-Liste durch, merkt sich, wo die kleinste Zahl darin liegt, und holt sie an den vordersten freien Platz. Der Platz davor ist damit endgültig richtig besetzt und wird nie wieder angefasst.

Selection-Sort mit 5 Zahlen

5

2

4

1

3

Los geht es.

Vergleiche: 0   Tausche: 0

Zahlen: 5Tempo: langsam

Ausgewählt wird also, bevor bewegt wird — daher Selection-Sort, nach dem englischen Wort für Auswahl.

zahlen = [5, 2, 4, 1, 3]

for i in range(len(zahlen)):
    kleinstes = i
    for j in range(i + 1, len(zahlen)):
        if zahlen[j] < zahlen[kleinstes]:
            kleinstes = j
    zahlen[i], zahlen[kleinstes] = zahlen[kleinstes], zahlen[i]

print(zahlen)

Beachte, was in kleinstes steht: nicht die kleinste Zahl, sondern ihr Index. Den Wert könntest du dir auch merken, aber du brauchst die Stelle, um am Ende tauschen zu können.

Quick-Sort: teilen statt durchlaufen

bleeptrack erklärt Quick-Sort — Video bei YouTube ansehen

Die ersten drei Verfahren arbeiten sich vergleichend durch eine Liste, die die ganze Zeit dieselbe bleibt. Quick-Sort macht etwas anderes: Es nimmt eine Zahl aus der Liste, das Pivot, und teilt alles Übrige in zwei Haufen — kleiner als das Pivot und größer als das Pivot. Dann macht es mit jedem Haufen dasselbe noch einmal, solange, bis ein Haufen nur noch aus einer Zahl besteht. Ein Haufen aus einer Zahl ist immer sortiert.

Von oben nach unten gelesen wird die Menge bei jedem Schritt kleiner, von unten nach oben gelesen setzt sie sich sortiert wieder zusammen: erst 1, dann 2, dann 3, 4, dann 7, dann 8, 9.

def quicksort(zahlen):
    if len(zahlen) < 2:
        return zahlen

    pivot = zahlen[0]
    kleiner = []
    groesser = []

    for i in range(1, len(zahlen)):
        if zahlen[i] < pivot:
            kleiner.append(zahlen[i])
        else:
            groesser.append(zahlen[i])

    return quicksort(kleiner) + [pivot] + quicksort(groesser)

Auffällig: Die Funktion ruft sich selbst auf. Das heißt Rekursion und ist erlaubt, solange es einen Fall gibt, in dem sie es nicht tut — hier die Liste mit weniger als zwei Elementen.

Rekursion

Eine Funktion heißt rekursiv, wenn sie sich selbst aufruft. Damit sie zum Ende kommt, braucht sie einen Fall, den sie ohne weiteren Aufruf beantworten kann — den Abbruchfall. Fehlt der, läuft das Programm, bis Python abbricht.

Proxmap-Sort: schätzen statt vergleichen

Alle bisherigen Verfahren haben eines gemeinsam: Sie vergleichen. Und man kann beweisen, dass ein Verfahren, das ausschließlich vergleicht, nicht wesentlich besser werden kann als Quick-Sort. Um schneller zu werden, muss man aufhören zu vergleichen.

Wie das geht, machst du selbst vor, sobald du im Adressbuch etwas suchst. Du fängst nicht bei A an und blätterst weiter. Du greifst sofort weit nach unten, weil du weißt, dass das S ungefähr dort liegt. Den Platz eines Namens schätzt du, statt ihn zu suchen — und triffst fast immer.

Genau das bekommt der Rechner jetzt beigebracht. Er schätzt nicht nach Gefühl, er rechnet die Schätzung aus. Hätte er für jeden möglichen Wert einen eigenen Ablageplatz, wäre die Sache trivial: jede Zahl auf ihren Platz, danach die Lücken entfernen, fertig. So viel Speicher will aber niemand ausgeben. Nehmen wir also für Werte bis 14 nur sechs Ablageplätze und schätzen:

Platz = Wert / größter Wert · Anzahl der Ablageplätze

Für die 10 sind das 10 / 14 · 6 ≈ 4.

Die dritte Zeile ist der Kern: Die 9 möchte auch auf Platz 4, aber dort liegt schon die 10. Also wird verglichen — die 9 ist kleiner, sie gehört weiter nach links. Sie bleibt auf Platz 4, die 10 wandert einen Platz weiter nach rechts. Wäre auch Platz 5 belegt gewesen, ginge dasselbe Spiel eins weiter. Und wer am rechten Rand ankommt, rutscht eben in die andere Richtung.

Zum Schluss werden die leer gebliebenen Plätze entfernt, und die Zahlen liegen sortiert da. Verglichen wurde dabei fast nichts — nur dort, wo zwei Zahlen denselben Platz wollten.

Womit Proxmap-Sort bezahlt

Je mehr Ablageplätze, desto seltener muss umgesteckt werden. In der Praxis hat sich bewährt, nur etwa 75 Prozent der Plätze zu belegen — man kauft Geschwindigkeit also mit Speicher.

Und man bezahlt ein zweites Mal, diesmal mit Wissen: Die Schätzformel oben trifft nur dann gut, wenn die Werte einigermaßen gleichmäßig über ihren Bereich verteilt sind. Ob das für deine Daten zutrifft, musst du vorher wissen — der Algorithmus merkt es nicht von allein.

Wo Proxmap versagt

1. Stell eine Menge aus zehn Zahlen zusammen, bei der fast alle auf demselben Ablageplatz landen. Schreib die zehn Zahlen auf.
2. Begründe in zwei Sätzen, warum die Schätzformel bei genau dieser Menge nichts mehr taugt.
3. Gib eine Formel an, mit der deine zehn Zahlen wieder gleichmäßig auf die sechs Plätze fallen.

Zurück an den Tisch

Hol den Zettel wieder hervor, auf dem steht, wie du am Anfang des Kapitels die sieben Karten geordnet hast. Damals hattest du keinen Namen für das, was du getan hast. Jetzt hast du fünf.

Was hast du eigentlich benutzt?

1. Lies deine eigene Beschreibung noch einmal und halte sie neben Bubble-Sort, Insertion-Sort und Selection-Sort. Welchem der drei kommt dein Vorgehen am nächsten? Belege deine Antwort mit einem Satz aus deiner Beschreibung.
2. Vergleicht eure Antworten in der Klasse. Fallen die Antworten auseinander oder nennen die meisten dasselbe Verfahren? Sucht nach einer Erklärung dafür.

Und damit die eigentliche Lehre dieses Kapitels: Es gibt kein bestes Sortierverfahren. Es gibt nur eines, das zu deinen Daten passt — für dreihundert Kontakte im Telefon taugt ein anderes als für die Milliarden Seiten, die eine Suchmaschine ordnet.

Noch mehr üben

Aufgabe

Aufgabe