Sortieren

---

Laufzeitmessung in Python

Verwendung der timeit-Bibliothek für die Hausaufgabe.

• Importiere das timeit-Modul: import timeit
• Teile den Algorithmus in die Initialisierungen und den Teil, dessen Geschwindigkeit gemessen werden soll. Beide Teile werden in jeweils einen (mehrzeiligen) String eingeschlossen:

 +--------+     +----+            setup = """            prog = """
 |  algo  | --> |init|                +----+                 +----+
 |        |     +----+                |init|                 |prog|
 |        |                           +----+                 +----+
 |        |     +----+             """                     """
 |        | --> |prog|            
 +--------+     +----+            

• aus den beiden Strings wird ein Timeit-Objekt erzeugt: t = timeit.Timer(prog, setup)
• Frage: Wie oft soll die Algorithmik wiederholt werden

z.B. N = 1000

• Zeit in Sekunden für N Durchläufe: K = t.timeit(N)

Zeit für 1 Durchlauf: K/N

Sortierverfahren

Motivation

Def: Ein Sortierverfahren ist ein Algorithmus, der dazu dient, die Elemente in einem Container in eine aufsteigende Reihenfolge zu bringen (siehe Wikipedia).

Anwendungen

• Sortierte Daten sind häufig Vorbedingungen für Suchverfahren (Speziell für effiziente Suchalgorithmen mit Komplexität <math>\mathcal{O}(log(N))</math>)
• Darstellung von Daten gemäß menschlicher Wahrnehmung
• Aus programmiertechnischer Anwendungssicht hat das Sortierproblem allerdings heute an Relevanz verloren, weil
  • gängige Programmiersprachen heute bereits geeignete Sortierfunktionen zur Verfügung stellen. Der Programmierer braucht sich deshalb in den meisten Fällen nicht mehr um die Implementierung von Sortieralgorithmen zu kümmern. In C/C++ sorgt dafür beispielsweise die Funktion std::sort.
  • die Hardware (z.B. Größe des RAM und der Festplatte) heute weniger limitierenden Charakter hat als vor 50 Jahren, so dass Standardsortierverfahren meist ausreichen, während komplizierte (z.B. speicher-sparende) Algorithmen nur noch in Ausnahmefällen nötig sind.
• Die Kenntnis grundlegender Sortieralgorithmen ist trotzdem immer noch nötig: Einerseits kann man vorgefertigte Bausteine nur dann optimal einsetzen, wenn man weiß, was hinter den Kulissen passiert und andererseits verdeutlicht gerade das Sortierproblem wichtige Prinzipien der Algorithmenentwicklung und -analyse in sehr anschaulicher Form.

Vorraussetzungen

Ordnungsrelation

Über den zu sortierenden Elementen muss eine Relation <math>\le</math> definiert sein, die die Axiome einer totalen Ordnung erfüllt (siehe Wikipedia). Eine totale Ordnung über einer Menge <math>M</math> ist eine binäre Relation <math>R \subseteq M \times M</math>, die transitiv, antisymmetrisch und total ist. Dass heißt, für alle <math> a,b,c \ \in M </math> gilt:

1. <math>a \le b \wedge b \le a \Rightarrow a=b </math> (antisymmetrisch)
2. <math>a \le b \wedge b \le c \Rightarrow a \le c </math> (transitiv)
3. <math>a \le b \vee b \le a </math> (total)

Bemerkung: aus 3. folgt <math> a \le a </math> (reflexiv)

Die Forderung, dass die Ordnung total sein muss, wird verständlich, wenn man ihr Gegenteil betrachtet: Ist die Ordnung nämlich nur partiell, gibt es Elemente <math>a, b</math>, die nicht vergleichbar sind. Die Relation <math>a \le b</math> kann dann das Ergebnis "unknown" liefern (statt true oder false), und das ist beim Sortieren nicht erlaubt.

Aus der Definition der Relation <math>\le </math> folgen automatisch Definitionen für die anderen Vergleichsrelationen <math><, \ge, >, =, \ne</math>, siehe Hausaufgabe.

Datenspeicherung

Wir nehmen an, dass die Daten in einem Array a vorliegen:

Array

       +---+---+---+---+---+---+---+---+---+
       |   |   |   |   |   |   |   |   |   |
       +---+---+---+---+---+---+---+---+---+
      \________________  ____________________/
                       \/
                   N Elemente

Datenelemente können über Indexoperation a[i] gelesen, überschrieben und miteinander vertauscht werden. Das hat den Vorteil, dass wir auf die Elemente in beliebiger Reihenfolge effizient zugreifen können. Dies ist für fast alle Sortieralgorithmen nützlich.

Früher wurden Daten oft in verketteten Listen gespeichert:

Vekettete Liste

       +---+     +---+     +---+
       |   | --> |   | --> |   | --> Ende
       +---+     +---+     +---+

Jeder Knoten der Liste enthält ein Datenelement und einen Zeiger auf den nächsten Knoten. Dadurch ist ein effizienter Zugriff nur auf den Nachfolger eines gegebenen Elements möglich. Zum effizienten Sortieren ist dann vor allem merge sort geeignet. Wir gehen in der Vorlesung nicht weiter auf verkettete Listen ein.

Nachbedingungen

Nach dem Sortieren erfüllen alle Elemente des Arrays folgendes Axiom:

Für beliebige Indizes <math>0 \le j < k < N-1</math> gilt: <math>a[j] \le a[k]</math>.

Ein Testprogramm kann somit die korrekte Sortierung überprüfen, indem es die Bedingung <math>a[j] \le a[k]</math> für alle <math>N(N-1)/2</math> möglichen Paare von Indizes <math>j,\ k</math> testet. In Wirklichkeit sind allerdings <math>N-1</math> Tests ausreichend, siehe Hausaufgabe.

Stabilität

Oft werden Arrays sortiert, die strukturierte Datenelemente enthalten. Beispielsweise könnten die Datenelemente den Typ Student haben, der aus dem Namen und der AlDa-Note zusammengesetzt ist. Das Array sei zunächst alphabetisch nach Namen sortiert:

 [("Adam", 1.3), ("Albrecht", 1.0), ("Meier", 1.3), ("Müller", 2.0), ("Wolf", 1.0)]

Wir wollen das Array nun nach Noten sortieren. Da aber einige Teilnehmer die gleiche Note haben, stellen wir zusätzlich die Forderung auf, dass die Namen mit gleicher Note alphabetisch sortiert bleiben sollen. Allgemein definiert man:

Def: Ein Sortierverfahren heißt stabil, wenn die relative Reihenfolge gleicher Schlüssel durch die Sortierung nicht verändert wird.

Im Beispiel erzeugt ein stabiles Sortierverfahren die Ausgabe

 [("Albrecht", 1.0), ("Wolf", 1.0), ("Adam", 1.3), ("Meier", 1.3), ("Müller", 2.0)]

während die Ausgabe

 [("Albrecht", 1.0), ("Wolf", 1.0), ("Meier", 1.3), ("Adam", 1.3), ("Müller", 2.0)]

nicht stabil ist (die Elemente ("Adam", 1.3), ("Meier", 1.3) sind vertauscht).

Selection Sort

Algorithmus

array = [...]  # zu sortierendes Array

for i in range(len(array)-1):
   min = i
   for j in range(i+1, len(array)):
      if a[j]< a[min]:
          min = j
   a[i], a[min] = a[min], a[i]  # Vertausche a[i] mit dem kleinsten rechts befindlichen Element
                                # Elemente links von a[i] und a[i] selbst befinden sich nun in ihrer endgültigen Position

Beispiel: Sortieren der Liste [S,O,R,T,I,N,G].

erste Iteration der äußeren Schleife, Zustand vor dem Vertauschen:
 i=0                     min
+---+---+---+---+---+---+---+
| S | O | R | T | I | N | G |
+---+---+---+---+---+---+---+

erste Iteration der äußeren Schleife, Zustand nach dem Vertauschen:
+---|---+---+---+---+---+---+
| G | O | R | T | I | N | S |
+---|---+---+---+---+---+---+

zweite Iteration der äußeren Schleife:
     i=1         min
+---|---+---+---+---+---+---+
| G | O | R | T | I | N | S |
+---|---+---+---+---+---+---+

weitere Iterationen:
         i=2         min
+---+---|---+---+---+---+---+
| G | I | R | T | O | N | S |
+---+---|---+---+---+---+---+ 

             i=3 min
+---+---+---|---+---+---+---+
| G | I | N | T | O | R | S |
+---+---+---|---+---+---+---+ 

                 i=4 min
+---+---+---+---+---+---+---+
| G | I | N | O | T | R | S |
+---+---+---+---+---+---+---+  
...

Laufzeit

Da in jeder Iteration der inneren Schleife ein Vergleich a[j]< a[min] durchgeführt wird, ist die Anzahl der Vergleiche ein gutes Maß für den Aufwand des Algorithmus und damit für die Laufzeit. Sei C(N) die Anzahl der notwendigen Vergleiche, um ein Array der Größe N zu sortieren. Die Arbeitsweise des Algorithmus kann dann so beschrieben werden: Führe N-1 Vergleiche aus, bringe das kleinste Element an die erste Stelle, und fahre mit dem Sortieren des Rest-Arrays (Größe N-1) rechts des ersten Elements fort. Dafür sind nach Definition noch C(N-1) Vergleiche nötig. Es gilt also:

<math>C(N) = C(N-1) + (N-1)</math>

C(N-1) können wir nach der gleichen Formel einsetzen, und erhalten:

<math>C(N) = C(N-2) + (N-2) + (N-1)</math>

Wir können in dieser Weise weiter fortfahren. Bei C(1) wird das Einsetzen beendet, denn für ein Array der Länge 1 sind keine Vergleiche mehr nötig, also C(1) = 0. Wir erhalten somit

<math>C(N) = C(N-3) + (N-3) + (N-2) + (N-1)</math>

<math>...</math>

<math>C(N) = C(1) + 1 + 2 + ...+ (N-2)+ (N-1)</math>

<math>C(N) = 0 + 1 + 2 + ...+ (N-2)+ (N-1)</math>

Nach der Gaußschen Summenformel ist dies

<math>C(N) = \frac {(N-1)N}{2}\approx \cfrac {(N^2)}{2}</math> (für große N).

In jedem Durchlauf der äußeren Schleife werden außerdem zwei Elemente ausgetauscht. Es gilt für die Anzahl der Austauschoperationen

<math>A(N)= N-1</math>

Stabilität

Selection Sort ist nicht stabil, weil die swap-Operation das Element a[i] nach hinten kopiert. Falls es ein Element a[k] gibt, so dass a[i] == a[k] und i < k < min, gelangt a[i] durch das swap hinter a[k], was nach Definition der Stabilität verboten ist.

Insertion Sort

• wird in der Übungsgruppe behandelt, siehe auch in der WikiPedia
• Erweiterung: Shell sort

Mergesort

Algorithmus

Zugrunde liegende Idee:

• Zerlege das Problem in zwei möglichst gleich große Teilprobleme ("Teile und herrsche"-Prinzip -- divide and conquer)
• Löse die Teilprobleme rekursiv
• Führe die Teillösungen über Mischen (merging) in richtig sortierter Weise zusammen.

Der Algorithmus besteht somit aus zwei Teilen

Zusammenführen -- merge

a und b sind zwei sortierte Listen, die in eine sortierte Ergebnisliste kombiniert werden.

def merge(a,b):
    c = []   # zunächst leere Ergebnisliste 
    i, j = 0, 0
    while i < len(a) and j < len(b):
        # wähle des kleinste der noch nicht angefügten Elemente
        if a[i] <= b[j]:
             c.append(a[i])
             i += 1
        else:
             c.append(b[j])
             j += 1
   # eine Liste ist jetzt aufgebraucht => der Rest der anderen wird einfach an c angehängt
   if i < len(a):
       c += a[i:]
   else:
       c += b[j:]
   return c

rekursives Sortieren

def mergeSort(a):  # a ist das zu sortierende Array
    if len(a) <= 1:
        return a   # Rekursionsabschluß: leere Arrays und Arrays mit einem Element müssen nicht sortiert werden
    else:
        left  = a[:len(a)/2]   # linkes Teilarray
        right = a[len(a)/2:]   # rechtes Teilarray
        leftSorted  = mergeSort(left)  # rekursives Sortieren der Teilarrays
        rightSorted = mergeSort(right) # ...
        return merge(leftSorted, rightSorted)  # Zusammenführen der Teilarrays

Bei der Sortierung mit Mergesort wird das Array immer in zwei fast gleich große Teile geteilt. → Es entsteht ein Binärbaum der Tiefe <math>\log_2 N</math>.

Beispiel: Sortieren der Liste [S,O,R,T,I,N,G].

Der Algorithmus läuft in der folgenden Skizze zunächst rekursiv von unten nach oben (Zerlegen in Teillisten), danach werden die sortierten Teillisten von oben nach unten zusammengeführt (diese sortierten Teillisten sind in der Skizze dargestellt).

Schritt 0:
 S 0 R T I N G     S    O R    T I    N     G    #Arraylänge: N/8    Vergleiche: 0
Schritt 1:          \  /   \  /   \  /     /
 OS RT IN G          OS     RT     IN     /      #Arraylänge: N/4    Vergleiche: 3 * 2 = 6
Schritt 2:             \    /        \   /       
 ORST GIN               ORST          GIN        #Arraylänge: N/2    Vergleiche: 4 + 3 = 7
                           \         /
Schritt3:                   \       /
 GINORST                     GINORST             #Arraylänge: N      Vergleiche: N     = 7

Laufzeit

Man erkennt an der Skizze, dass der Rekursionsbaum für ein Array der Länge N die Tiefe log N hat. Auf jeder Ebene werden weniger als N Vergleiche ausgeführt, so dass insgesamt weniger als N*log N Vergleiche benötigt werden. Dies ist natürlich wesentlich effizienter als die (N-1)*N/2 Vergleiche von Selection Sort. Mathematisch exakt kann man die Anzahl der Vergleiche durch die folgende Rekursionsformel berechnen:

<math>C(N) = C(\lfloor N/2\rfloor) + C(\lceil N/2\rceil) + N</math>

Der Aufwand ergibt sich aus dem Aufwand für die beiden Teilprobleme plus dem Aufwand für N Vergleiche beim Zusammenführen der sortierten Teillisten. Dabei stehen die Zeichen <math>\lfloor \rfloor</math> und <math>\lceil \rceil</math> für abrunden bzw. aufrunden, weil ein Problem mit ungeradem N nicht in zwei exakt gkeiche Teile geteilt werden kann. Um diese Komplikation zu vermeiden, beschränken wir uns im folgenden auf den Fall <math>N = 2^n</math> (mit etwas höherem Aufwand kann man zeigen, dass diese Einschränkung nicht notwendig ist und die Resultate für alle N gelten). Die vereinfachte Aufwandsformel lautet:

<math>C(N) = 2 C(N/2) + N</math>

Durch Einsetzen der Formel für N/2 erhalten wir:

<math>C(N) = 2 (2 C(N/4) + N/2) + N = 4 C(N/4) + N + N</math>

<math>C(N) = 4 (2 C(N/8) + N/4) + N + N = 8 C(N/8) + N + N + N</math>

<math>...</math>

Die Rekursion endet, weil für ein Array der Größe <math>N=1</math> keine Vergleiche mehr benötigt werden, also <math>C(1) = 0</math> gilt. Mit <math>N=2^n</math> ist dies aber gerade nach <math>n = \log_2 N</math> Zerlegungen der Fall. Merge Sort benötigt also

<math>C(N) = N + ... + N = n \cdot N = N\cdot \log_2 N</math>

Vergleiche.

Weitere Eigenschaften von MergeSort

• Mergesort ist stabil: wegen des Vergleichs a[i] <= b[j] wird die Position gleicher Schlüssel im Algorithmus merge(a,b) nicht verändert -- bei gleichem Schlüssel hat, wie gefordert, das linke Element Vorrang.
• Mergesort ist unempfindlich gegenüber der ursprünglichen Reihenfolge der Eingabedaten. Grund dafür ist
  • die vollständige Aufteilung des Ausgangsarrays in Arrays der Länge 1 und
  • dass merge(a,b) die Vorsortierung nicht ausnutzt, d.h. die Komplexität von merge(a,b) ist sortierungsunabhängig.
• Diese Eigenschaft kann unerwünscht sein, wenn ein Teil des Arrays oder gar das ganze Array schon sortiert ist. Es wird nämlich in jedem Fall das ganze Array neu sortiert. Die Python-Sortierfunktion (list.sort()), die Merge Sort verwendet, implementiert deshalb eine Reihe von Optimierungen, damit das Sortieren von (teilweise) sortierten Arrays schneller geht als das Sortieren zufälliger Arrays, weil dieser Fall in der Praxis sehr häufig vorkommt.
• Merge Sort eignet sich für das Sortieren von verketteten Listen, weil die Listenelemente stets von vorn nach hinten durchlaufen werden. In diesem Fall muss merge(a, b) keine neue Liste c für das Ergebnis anlegen, sondern kann einfach die Verkettung der Listenelemente von a und b entsprechend anpassen. In diesem Sinne arbeitet Merge Sort auf verketten Listen "in place", d.h. es wird kein zusätzlicher Speicher benötigt.
• Im Gegensatz dazu benötigt merge(a,b) zusätzlichen Speicher für das Ergebnis c, wenn die Daten in einem Array gegeben sind.

Merge Sort in Python

Die Funktion list.sort() in Python benutzt intern Merge Sort, allerdings in einer hochoptimierten Fassung. Die Optimierungen betreffen die Beschleunigung der Sortierung von teilweise sortierten oder kleinen Arrays sowie die Verringerung des Speicherverbrauchs. Eine ausführliche Diskussion der Python-Lösung findet man im File listsort.txt im Python-SVN.

Quicksort

• Quicksort wurde in den 60er Jahren von Charles Antony Richard Hoare entwickelt. Es gibt viele Implementierungen von Quicksort (vgl. Quicksort in Wikipedia).
• Dieser Algorithmus gehört zu den "Teile und herrsche"-Algorithmen (divide-and-conquer) und ist der Standardalgorithmus für Sortieren.
• Im Gegensatz zu Merge Sort wird das Problem aber nicht immer in zwei fast gleich große Teilprobleme zerlegt. Dadurch vermeidet man, dass zusätzlicher Speicher benötigt wird (Quick Sort arbeitet auch für Arrays "in place"). Allerdings erkauft man sich dies dadurch, dass Quick Sort bei ungünstigen Eingaben (die Bedeutung von "ungünstig" ist je nach Implementation verschieden) nicht effizient arbeitet. Da solche Eingaben jedoch in der Praxis fast nie vorkommen, tut dies der Beliebtheit von Quicksort keinen Abbruch.

Algorithmus

Wie Merge Sort arbeitet Quick Sort rekursiv. Hier werden die Daten allerdings zuerst vorbereitet (in der Funktion partition), und danach erfolgt der rekursive Aufruf:

def quicksort(a, l, r): 
    """a ist das zu sortierende Array, 
       l und r sind die linke und rechte Grenze des zu sortierenden Bereichs"""

     if r > l:                     # Rekursionsabschluss: wenn r <= l, ist der Bereich leer und muss nicht mehr sortiert werden
         i = partition(a, l, r)    # i ist der Index des sog. Pivot-Elements (s. u.)
         quicksort(a, l, i-1)      # rekursives Sortieren der beiden Teilarrays
         quicksort(a, i+1, r)      # ...

Der Schlüssel des Algorithmus ist offensichtlich die Funktion partition. Diese wählt ein Element des Arrays aus (das Pivot-Element) und bringt es an die richtige Stelle (also an den Index i, der von partition zurückgegeben wird). Außerdem stellt sie sicher, dass alle Elemente in der linken Teilliste (Index < i) kleiner als a[i], und alle Elemente in der rechten Teilliste größer also a[i] sind:

1. <math>a[i]</math> ist sortiert, d.h. dieses Element ist am endgültigen Platz.
2. <math>\forall x \in \left\{ a \left[ l \right] , ... a \left[ i-1 \right] \right\} : x \leq a \left[ i \right]</math>
3. <math>\forall x \in \left\{ a \left[ i+1 \right], ... a \left[ r \right] \right\} : x \geq a \left[ i \right]</math>

         l                               r
       +---+---+---+---+---+---+---+---+---+
Array: |   |   |   |   |\\\|   |   |   |   |
       +---+---+---+---+---+---+---+---+---+
        \______  _____/  i  \______  _____/ 
               \/                  \/
            <=a[i]               >=a[i]             (a[i] ist das Pivot-Element)

Die Position von i richtet sich also offensichtlich danach, wie viele Elemente im Bereich l bis r kleiner bzw. größer als das gewählte Pivot-Element sind. Der Wahl eines guten Pivot-Elements kommt demnach eine große Bedeutung zu (s.u.).

In der einfachsten Version wird partition wie folgt definiert:

def partition(a, l, r):
    pivot = a[r]     # Pivot-Element. Hier wird willkürlich das letzte Element verwendet.
    i  = l           # i und j sind Laufvariablen
    j  = r - 1

    while True:
        while i < r and a[i] <= pivot:
            i += 1               # finde von links das erste Element > pivot
        while j > l and a[j] >= pivot:
            j -= 1               # finde von rechts den ersten Eintrag < pivot
        if i >= j:               # keine weiteren Elemente zum Tauschen
            break                # => Schleife beenden      
        a[i], a[j] = a[j], a[i]  # a[i] und a[j] sind beide auf der falschen Seite des Pivot => vertausche sie
    a[i], a[r] = a[r], a[i]      # bringe das Pivot an seine endgültige Position i
                                 # wegen a[i] >= pivot gehört das bisherige a[i] auf die rechte Seite
    return i                     # gebe Pivot-Position zurück

Die folgende Skizze verdeutlicht das Austauschen

                                         p
       +---+---+---+---+---+---+---+---+---+
Array: |   |   |   |   |   |   |   |   |\\\|
       +---+---+---+---+---+---+---+---+---+
       ------> a[i]>p          a[j]<p <-----
                 |               |
                 +---------------+
      Diese zwei Elemente werden ausgetauscht.

Dies wird wiederholt, bis sich die Zeiger treffen oder einander überholt haben. Am Schluss wird das Pivot-Element an die richtige Stelle verschoben:

                         p
       +---+---+---+---+---+---+---+---+---+
Array: |   |   |   |   |\\\|   |   |   |   |
       +---+---+---+---+---+---+---+---+---+
                         i
       -----------------> <-----------------
 

Beispiel: Partitionieren des Arrays [A,S,O,R,T,I,N,G,E,X,A,M,P,L,E] mit Pivot 'E'.

 l,i -->                                          <-- j   r
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| A | S | O | R | T | I | N | G | E | X | A | M | P | L | E |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

      i <--------- Vertauschen ---------> j               r
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| A | S | O | R | T | I | N | G | E | X | A | M | P | L | E |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

          i <-------------------> j                       r
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| A | A | O | R | T | I | N | G | E | X | S | M | P | L | E |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

          j   i                                           r
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| A | A | E | R | T | I | N | G | O | X | S | M | P | L | E |   --> Hier wird die 
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+       Schleife verlassen.

          j   i <---------------------------------------> r
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| A | A | E | R | T | I | N | G | O | X | S | M | P | L | E |   
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

              i                                           r
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| A | A | E | E | T | I | N | G | O | X | S | M | P | L | R |   --> Hier wird partition() beendet.
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Weitere ausführliche Erklärungen der Implementation findet man bei Sedgewick.

Laufzeit

Die allgemeine Rekursionsformel für die Laufzeit der äußeren Schleife lautet

<math>C(N) = (N+1) + C(k-1) + C(N-k)</math>

wobei <math>k</math> der Index des Pivotelements nach der Ausführung von partition() ist. Der Term <math>N+1</math> ist die Anzahl der Vergleiche, die partition() benötigt: Da normalerweise (falls es keine weiteren Elemente mit dem Wert des Pivots gibt) am Ende von partition() die Bedingung j == i-1 gilt, wurden die Elemente a[i] und a[j] jeweils zweimal mit dem Pivot verglichen (einmal in der i-Schleife und einmal in der j-Schleife), während die übrigen <math>N-3</math> Elemente nur einmal verglichen wurden, also insgesamt <math>N-3+4=N+1</math> Vergleiche.

Allerdings können wir die Rekursionsformel nicht auflösen, ohne <math>k</math> zu kennen. Wir müssen deshalb Annahmen über <math>k</math> machen und untersuchen als erstes den schlechtesten Fall, dass <math>k</math> immer am Rand des Bereichs liegt. Dies tritt z.B. dann ein, wenn das Array bereits vor Beginn sortiert war. Dann ist das Pivot-Element a[r] immer das größte Element jedes Bereichs und verbleibt nach der Ausführung von partiion() an dieser Position, so dass <math>k=N</math> gilt. Die Anzahl der Vergleiche ergibt sich dann als

<math>C(N) = (N+1) + C(N-1) + C(0)</math>

Das Sortieren eines leeren Arrays erfordert gar keine Vergleiche, es gilt also

<math>C(0) = 0</math>

<math>C(N) = (N+1) + C(N-1)</math>

Dies ist fast die gleiche Formel wie bei Selection Sort, und durch sukzessives Einsetzen erhalten wir:

<math>C(N) = (N+1) + (N) + (N-1) + ... + 1 = (N+2)(N+1) / 2</math>

In diesem Fall ist Quick Sort also noch langsamer als Selection Sort. Wir beschreiben unten, wie man verhindert, dass dieser schlechteste Fall jemals auftritt.

Der bestmögliche Fall tritt ein, wenn partition() das Array in zwei gleich große Hälften teilt, so dass <math>k=N / 2</math> gilt. Dann ist die Anzahl der Vergleiche

<math>C(N) = (N+1) + C(N/2-1) + C(N/2)</math>

<math>C(N) \approx N + 2 C(N/2)</math>

Dies ist die gleiche Formel wie bei Merge Sort, und durch sukzessives Einsetzen erhalten wir

<math>C(N) \approx N\log_2(N)</math>

wie bei Merge Sort. In der Praxis ist Quick Sort sogar noch etwas schneller, weil die Daten nicht in ein temporäres Array kopiert werden müssen. Man sagt, dass Quick Sort "in place", also im zu sortierenden Array selbst, operiert (dies gilt auch für Selection Sort).

Es stellt sich nun die Frage, welcher Fall in der Praxis typischerweise auftritt - der schlechte oder der günstige? Als "typischen Fall" betrachten wir die Situation, dass das Array zu Beginn zufällig sortiert war. Bei zufälliger Sortierung hat jeder Index die gleiche Wahrscheinlichkeit, im Ende von partition() als Pivot-Position herauszukommen. Wir mitteln deshalb über alle möglichen Positionen:

<math>C(N) = (N+1) + \frac{1}{N} \sum_{k=1}^{N} \left[ C(k-1) + C(N-k) \right]</math> für <math> N>0</math>

wobei <math>k</math> über alle möglichen Teilungspunkte läuft. Die Summe (der mittlere Aufwand über alle möglichen Zerlegungen) kann vereinfacht werden zu

<math>\frac{1}{N} \sum_{k=1}^{N} \left[ C(k-1) + C(N-k) \right] = 2 \frac{1}{N} \sum_{k=1}^{N} C(k-1) </math>

weil alle Terme der Summe zweimal vorkommen (beispielsweise ergibt sich <math>C(1)</math> einmal aus <math>C(k-1)</math> für <math>k=2</math>, und einmal aus <math>C(N-k)</math> für <math>k=N-2</math>). Die Auflösung der Formel ist etwas trickreich. Wir multiplizieren zunächst beide Seiten mit N:

<math>

N \cdot C(N) = N \left[ (N+1) + \frac{2}{N} \sum_{k=1}^{N} C(k-1) \right] = N (N+1) + 2\; \sum_{k=1}^{N} C(k-1)</math>

Durch die Substitution <math>N \rightarrow N-1</math> erhalten wir die entsprechende Formel für N-1:

<math>

(N-1) \cdot C(N-1) = (N-1) N + 2\; \sum_{k=1}^{N-1} C(k-1)</math>

Wir subtrahieren die Formel für N-1 von der Formel für N und eliminieren dadurch die Summe (nur der letzte Summend der ersten Summe bleibt übrig):

<math>

\begin{array}{rcl} N \cdot C(N) - (N-1) \cdot C(N-1) &=& N(N+1) + 2\;\sum_{k=1}^{N} C(k-1) - (N-1) N - 2\;\sum_{k=1}^{N-1} C(k-1)\\ &&\\ N \cdot C(N) - (N-1) \cdot C(N-1) &=& N(N+1) - (N-1) N + 2 C(N-1) \end{array} </math> Nach Vereinfachung erhalten wir die rekurrente Beziehung

<math>

N \cdot C(N) = (N+1)\cdot C(N-1) + 2 N</math> Wir teilen jetzt beide Seiten durch <math>(N+1)N</math>

<math>

\frac{C(N)}{N+1} = \frac{C(N-1)}{N} + \frac{2}{N+1} </math> Sukzessives Einsetzen der Formel für <math> C(N-1), C(N-2) </math> etc. bis <math>C(1)=0</math> liefert

<math>

\frac{C(N)}{N+1} = \frac{C(N-2)}{N-1} + \frac{2}{N} + \frac{2}{N+1} = \frac{C(1)}{2} + \sum_{k=2}^N\frac{2}{k+1} </math> Für hinreichend große N kann die Summe sehr genau durch ein Integral approximiert werden. Der konstante Term kann für große N vernachlässigt werden:

<math>

\frac{C(N)}{N+1} \approx 2 \sum_{k=1}^{N} \frac{1}{k+1} - 1 \approx 2 \int_1^N \frac{1}{k} dk = 2 \cdot \ln(N)</math> Somit benötigt Quick Sort im typischen Fall

<math>C(N)\approx 2 N\cdot\ln(N) \approx 1.38 N\cdot\log_2(N)</math>

Vergleiche. Quick Sort ist demnach für den praktischen Einsatz geeignet, weil es sich im typischen Fall fast genauso verhält wie im günstigsten Fall.

Verbesserungen des Quicksort-Algorithmus

Beseitigung der Rekursion

Eine Verbesserung beseitigt die Rekursion durch Verwendung eines Stacks. Nach jeder Partitionierung wird das größere Teilintervall auf dem Stack abgelegt und das kleinere Teilintervall direkt weiterverarbeitet (hierdurch wird sichergestellt, dass die maximale Größe des Stacks minimiert wird).

def quicksortNonRecursive(a, l, r):
    stack = [(l,r)]  # initialisiere den Stack
    while len(stack) > 0:
        if r > l:
            i = partition(a, l, r)
            if (i-l) > (r-i):
                stack.append((l,i-1))
                l = i+1
            else:
                stack.append((i+1, r))
                r = i-1
        else:
            l, r = stack.pop()

Die ist die Methode der Endrekursionsbeseitigung, die wir im Kapitel Iteration versus Rekursion ausführlich behandeln. Die folgende Skizze verdeutlicht die Verwendung des Stacks.

+---+---+---+---+---+---+---+
| Q | U | I | C | K | S | O |
+---+---+---+---+---+---+---+

             
+---+---+---+===+---+---+---+
| K | C | I |=O=| Q | S | U |
+---+---+---+===+---+---+---+
                 \_________/
                     push

+---+===+---+
| C |=I=| K |
+---+===+---+
         \_/
         push

+===+
|=C=|
+===+

        +===+
        |=K=|
        +===+

                +---+---+===+
                | Q | S |=U=|
                +---+---+===+

                +---+===+
                | Q |=S=|
                +---+===+

                +===+
                |=Q=|
                +===+
        
+---+---+---+---+---+---+---+
| C | I | K | O | Q | S | U |  
+---+---+---+---+---+---+---+

Alternatives Sortieren kleiner Intervalle

Für kleine Arrays (bis zu einer gegebenen Größe K) ist das "Teile und herrsche"-Prinzip nicht die effizienteste Herangehensweise. Insbesondere kann man ein Array mit maximal 3 Elementen direkt sortieren:

def sortThree(a, l, r):
    if r > l and a[l+1] < a[l]:          # Stelle sicher, dass a[l] und a[l+1] relativ zueinander sortiert sind.
        a[l], a[l+1] = a[l+1], a[l]
    if r == l + 2:
        if a[r] < a[l]:                  # Stelle sicher, dass a[l] und a[r] relativ zueinander sortiert sind.
            a[l], a[r] = a[r], a[l]      # Danach ist a[l] auf jeden Fall das kleinste Element.
        if a[r] < a[r-1]:                # Stelle sicher, dass a[r-1] und a[r] relativ zueinander sortiert sind.
            a[r], a[r-1] = a[r-1], a[r]  # Jetzt ist a[r] auf jeden Fall das größte Element und das Array damit sortiert.

In die Funktion quicksort() wird jetzt ein Aufruf dieser Funktion eingefügt:

    if r > l + 2:
        # wie bisher
    else:
        sortThree(a, l, r)

Eine Optimierung für kleine Arrays wird für alle komplexen Sortieralgorithmen (also auch Merge Sort) gern verwendet, weil der zusätzliche Verwaltungsaufwand dieser Algorithmen bei kleinen Arrays nicht mehr durch den Geschwindigkeitsgewinn kompensiert wird. Meist kommt für kleine K (insbesondere am Ende der Rekursion, wenn weniger als 10 oder 20 Elemente übrig sind) Insertion Sort zum Einsatz.

Günstige Selektion des Pivot-Elements

Durch geschickte Wahl des Pivot-Elements kann man erreichen, dass der ungünstigste Fall (quadratische Laufzeit) nur mit sehr kleiner Wahrscheinlichkeit eintritt. Zwei Möglichkeiten haben sich bewährt:

1. Anstatt des letzten Elements des Teilarrays wählt man ein zufälliges Element (mit Hilfe eines Zufallszahlengenerators). Dadurch wird Quick Sort unempfindlich gegenüber bereits sortierten Arrays, weil die Teilung im Mittel wie bei einem zufällig sortierten Array erfolgt (typischer Fall in obiger Laufzeitberechnung).
2. Median (mittlerer Wert) von drei Kandidaten: Sortiere zunächst nur 3 willkürlich gewählte Elemente (z.B. a[l], a[(l+r)/2] und a[r]) und wähle den nach der Sortierung mittleren als Pivot ("median-of-three"-Methode). Dadurch wird es sehr unwahrscheinlich, dass man immer ein ungünstiges Pivot erwischt. Ist das Array z.B. bereits sortiert, kommt als Median immer das Element a[(l+r)/2] heraus, so dass alle Abschnitte in der Mitte geteilt werden - der günstigste Fall. Um noch sicherer zu gehen, kann man auch mehr Kandidaten (z.B. neun) wählen.

In beiden Fällen ist es praktisch ausgeschlossen, dass ein Eingabearray so angeordnet ist, dass in jedem Teilarray gerade das kleinste oder größte Element als Pivot gewählt wird. Nur dann könnte der ungünstigste Fall jedoch eintreten, was somit effektiv verhindert wird. Sollte es dennoch einmal schief gehen, kann man immer noch die Anzahl der Aufrufe von partition() mitzählen und zu einem anderen Sortieralgorithmus wechseln (z.B. zu Merge Sort oder Heap Sort, die auch im schlechtesten Fall schnell sind), wenn diese Zahl eine kritische Grenze (z.B. <math>a \cdot \log_2 N</math> für ein geeignetes <math>a</math>) überschreitet. Fast immer wird aber Quick Sort schneller sein als die Alternativen.

Quick Sort in C++

Die Implementation der C++-Standardfunktion std::sort(), die mit dem Gnu-Compiler mitgeliefert wird, benutzt intern Introsort, eine hochoptimierte Kombination von Quicksort und Heap Sort.

Nächstes Thema