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
3.Stunde am 16.04.2008
Sortierverfahren
Motivation
Def: Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren.
- Literatur, siehe Sortierverfahren; Bubblesort 1956, Quicksort 1962. Librarysort 2004
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 da
- gängige Programmiersprachen heute typunabhängige Algorithmen 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++ sorgen dafür beispielsweise Methoden aus der STL.
- Festplatten / Hauptspeicher heute weniger limitierenden Charakter haben, so dass Standardsortierverfahren meist ausreichen, während komplizierte, speicher-sparende Sortieralgorithmen nur noch selten benötigt werden.
- 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/Spielregeln
Mengentheoretische Anforderungen
Definition Totale Ordnung / Total geordnete Menge:
Eine Totale Ordnung / Total geordnete Menge ist eine binäre Relation
<math>R \subseteq M \times M</math> über einer Menge <math>M</math>, die transitiv, antisymmetrisch und total ist.
<math>R</math> sei dargestellt als infix Notation <math>\le </math> dann, falls M total geordnet, gilt
<math> \forall a,b,c \ \epsilon M </math>
(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)
In Wikipedia zu diesem Thema eine anscheinend gute Seite: Ordnungsrelation
Datenspeicherung
Die Daten liegen typischerweise in Form von Arrays oder verketteten Listen vor. Je nach Datenstruktur sind andere Sortieralgorithmen am besten geeignet.
- Array
+---+---+---+---+---+---+---+---+---+
|///| | | | | | | |///|
+---+---+---+---+---+---+---+---+---+
\________________ ____________________/
\/
N
Datenelemente können über Indexoperation a[i] gelesen, überschrieben und miteinander vertauscht werden. Vorteil: Die Zugriffsreihenfolge auf die Datenelemente ist beliebig. Nachteil: Einfügen oder Löschen von Elementen aus dem Array ist relativ aufwändig.
- Vekettete Liste
+---+ +---+ +---+
| | --> | | --> | | --> Ende
+---+ +---+ +---+
Jeder Knoten der Liste enthält ein Datenelement und einen Zeiger auf den nächsten Knoten. Vorteil: Einfügen und Löschen von Elementen ist effizient möglich. Nachteil: effizienter Zugriff nur auf den Nachfolger eines gegebenen Elements, d.h. Zugriffsreihenfolge ist nicht beliebig.
Stabilität
Ein Sortierverfahren heißt stabil falls die relative Reihenfolge gleicher Schlüssel durch die Sortierung nicht verändert wird.
Beispiel: Sortiere eine Liste von Paaren [(3,7), (4,2), (4,1), (2,2), (2,8)], wobei die Reihenfolge nur durch das erste Element (Schlüsselelement) jeden Paares festgelegt wird. Dann erzeugt ein stabiles Sortierverfahren die Ausgabe
[(2,2), (2,8), (3,7), (4,2), (4,1)]
während die Ausgabe
[(2,2), (2,8), (3,7), (4,1), (4,2)]
nicht stabil ist (die Paare (4,1), (4,2) sind vertauscht).
Charakterisierung der Effizienz von Algorithmen
- (a) Komplexität O(1), O(n), etc. wird in Kapitel Effizienz erklärt.
- (b) Zählen der notwendigen Vergleiche
- (c) Messen der Laufzeit mit 'timeit' (auf identischen Daten)
Rekursive Beziehungen zerlegt die ursprünglichen Probleme in kleinere Probleme und wendet den Algorithmus auf die kleineren Probleme an; daraufhin werden die Teilprobleme zur Lösung des Gesamtproblems verwendet. d.h. Laufzeit (operativer Vergleich) für N Eingaben hängt von der Laufzeit der Eingaben für die Teilprobleme ab.
Aufwand
(i) rekursives/ lineares Durchlaufen der Eingabedaten, Bearbeitung einzelner Elemente
C(N)= C(N-1)+ N ; N>1, C(1)= 1 +---+---+---+---+---+---+---+---+---+
= C(N-2) +(N-1)+ N | 7 | 3 | 2 | 5 | 6 | 8 | 1 | 4 | 2 |
= C(N-3) + (N-2) + (N-1) + N +---+---+---+---+---+---+---+---+---+
= ... ________________________/
= C(1) + 2+...+(N-1) +N /
+---+---+---+---+---+---+---+---+---+
N(N+1) N² | 1 | 3 | 2 | 5 | 6 | 8 | 7 | 4 | 2 |
= ----- ~ -- +---+---+---+---+---+---+---+---+---+
2 2
(ii) rekursives halbieren der Menge der Eingabedaten
C(N)= C(N/2)+1 ; N>1, C(1)=0
Aus Gründen der Einfachheit sei N = 2^n
C(N)= C(2^n)= C(<math>2^{n-1}</math>) + 1
= C(<math>2^{n-1}</math>) + 1 + 1
= ...
= C(<math>2^0</math>) + n
= n
= <math>log_2 N</math>
+---+---+---+---+-|-+---+---+---+---+
| | | | | | | | | |
+---+---+---+---+-|-+---+---+---+---+
+---+---+---+---+
| | | | |
+---+---+---+---+
+---+---+ +---+
| | | -> | |
+---+---+ +---+
(iii) rekursives halbieren, lineare Bearbeitung, jedes Elements
<math>C(N) = 2C(N/2) + N;\;N > 1,\,C(1) = 1</math>
Sei <math>N = 2^n</math>.
<math>\Rightarrow C(2^n) = 2C(2^{n-1}) + 2^n</math>
<math>\begin{align}
\Rightarrow \frac{C(2^n)}{2^n} &= \frac{C(2^{n-1})}{2^{n-1}} + 1 \\
&= \frac{C(2^{n-2})}{2^{n-2}} + 1 + 1 \\
&= \frac{C(2^{n-3})}{2^{n-3}} + 1 + 1 + 1 \\
&= \dots \\
&= \frac{C(1)}{1} + (n-1) \\
&= 1
\end{align}</math>
<math>\Rightarrow C(2^n) = 2^n\cdot n</math>
<math>\Rightarrow C(N) = N\cdot \log(N)</math>
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:
- <math>a[i]</math> ist sortiert, d.h. dieses Element ist am endgültigen Platz.
- <math>\forall x \in \left\{ a \left[ l \right] , ... a \left[ i-1 \right] \right\} : x \leq a \left[ i \right]</math>
- <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:
- 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).
- 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.
