Sortieren durch Zerlegen / Quicksort
Ein Sortierspiel
Anton, Britta, Carlo, ... wollen sich der Größe nach in einer Reihe aufstellen. Zuerst werden alle genau vermessen.

Das Spiel läuft jetzt so ab:
Eine Person (z.B. die erste in der Reihe) wird als Vergleichsperson ausgewählt. Im vorliegenden Beispiel ist das Anton.

Alle anderen ordnen sich links bzw. rechts von der Vergleichsperson ein, je nachdem, ob sie kleiner oder größergleich als die Vergleichsperson sind.

Anton bleibt jetzt auf seiner Position. Er nimmt nicht mehr an weiteren Spielrunden teil. Dasselbe Spiel wird jetzt im linken und im rechten Bereich durchgeführt: Eine Person (z.B. die erste in der Reihe) wird wiederum als Vergleichsperson ausgewählt.

Und so weiter ...
Aufgabe 1
Spielt das Sortierspiel selbst durch. Wann ist das Spiel beendet? Welche Extremfälle können während des Spiels auftreten? Funktioniert das Sortierspiel dann auch noch?
Die Grundidee
Gegeben ist eine Liste mit vergleichbaren Elementen. Ein Element der Liste (z.B. das erste Element) wird ausgewählt. Die Restliste wird dann gemäß dieses Elements in zwei Teillisten aufgeteilt: die Liste der Elemente der Restliste, die kleiner als das ausgewählte Element sind sowie die Liste der Elemente der Restliste, die nicht kleiner (d.h. größer oder gleich) als das ausgewählte Element sind. Dieser Vorgang wird mit den Teillisten völlig analog fortgesetzt.
25 17 32 56 25 19 8 66 29 6 20 29 ^ 17 19 8 6 20 | 25 | 32 56 25 66 29 29 ^ | | ^ | | 8 6 | 17 | 19 20 | | 25 29 29 | 32 | 56 66 ^ | | ^ | | ^ | | ^ | | | | | | 6 | 8|| ||19 | 20 | ||25 | 29 29 | ||56 | 66 | || | | | || | ^ | || | | || | | | || ||29 | 29 | || |
Die folgende Abbildung soll die Grundidee des Sortierverfahrens Sortieren durch Zerlegen
noch einmal verdeutlichen:

Aufgabe 2
Führe das Sortierverfahren Sortieren durch Zerlegen
am folgenden Beispiel durch.
Protokolliere die einzelnen Schritte wie oben gezeigt.
35 28 41 7 14 50 33 21 21 60 18 12 ^
Ablaufmodellierung mit mehreren Listen
Das oben erläuterte Sortierverfahren soll jetzt mit einem Algorithmus beschrieben werden.
Informell lässt sich dieser Sortierablauf so beschreiben:
ALGORITHMUS quicksort
Übergabe: Liste L
wenn die Liste L mehr als ein Element hat:
# zerlegen
wähle als Pivotelement p das erste Element der Liste aus
erzeuge Teillisten K und G aus der Restliste (L ohne p) mit:
- alle Elemente aus K sind kleiner als das Pivotelement p
- alle Elemente aus G sind größergleich als das Pivotelement p
# Quicksort auf die verkleinerten Listen anwenden
KSortiert = quicksort(K)
GSortiert = quicksort(G)
# zusammensetzen
LSortiert = KSortiert + [p] + GSortiert
sonst:
LSortiert = L
Rückgabe: LSortiert
Aufgabe 3
Implementiere den Algorithmus quicksort
.
Ablaufmodellierung mit einer Liste
Quicksort lässt sich auch mit Vertauschungen von Elementen in der Ausgangsliste realisieren:
ALGORITHMUS quicksort
Übergabe: Liste L, Indexbereich
wenn die Liste L nicht leer ist:
# zerlegen
wähle als Pivotelement p das erste Element der Liste aus
tausche Elemente innerhalb L so, dass eine Zerlegung entsteht mit:
- L = K + G
alle Elemente aus K sind kleinergleich als das Pivotelement p
alle Elemente aus G sind größergleich als das Pivotelement p
K und G enthalten mindestens ein Element
# Quicksort auf die verkleinerten Listen anwenden
L = quicksort(L, Indexbereich von K)
L = quicksort(L, Indexbereich von G)
Rückgabe: L
Die Implementierung ist hier etwas schwieriger:
def quicksort(L, anfang, ende):
if len(L) > 1:
#print('Quicksort', L[anfang:(ende+1)])
pivot = L[anfang]
links = anfang
rechts = ende
while links <= rechts:
while L[links] < pivot:
links = links+1
while L[rechts] > pivot:
rechts = rechts-1
if links <= rechts:
if links < rechts:
h = L[links]
L[links] = L[rechts]
L[rechts] = h
links = links+1
rechts = rechts-1
if rechts < anfang:
rechts = anfang
#print(' ', L[anfang:rechts+1], L[links:(ende+1)])
if anfang < rechts:
L = quicksort(L, anfang, rechts)
if links < ende:
L = quicksort(L, links, ende)
return L
# Test
L = [25, 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29]
print(L)
L = quicksort(L, 0, len(L)-1)
print(L)
Aufgabe 4
Teste diese Implementierung. Teste sie auch mit den Ausgabeanweisungen, die in der Funktionsdefinition oben noch auskommentiert sind. Erkläre die ausgegebenen Werte.