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.