Sortieren: Difference between revisions
m (typos) |
m (→Mengentheoretische Anforderungen: Formeln verschönert) |
||
| Line 48: | Line 48: | ||
<math>R</math> sei dargestellt als infix Notation <math>\le </math> dann, falls M total geordnet, gilt | <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> <br/> | <math> \forall a,b,c \ \epsilon M </math> <br/> | ||
(1) <math>a \le b \ | (1) <math>a \le b \wedge b \le a \Rightarrow a=b </math> (antisymmetrisch)<br/> | ||
(2) <math>a \le b \ | (2) <math>a \le b \wedge b \le c \Rightarrow a \le c </math> (transitiv)<br/> | ||
(3) <math>a \le b \ | (3) <math>a \le b \vee b \le a </math> (total) <br/> | ||
Bemerkung: aus (3) folgt <math> a \le a </math> (reflexiv) <br/> | Bemerkung: aus (3) folgt <math> a \le a </math> (reflexiv) <br/> | ||
Revision as of 13:53, 22 July 2008
Laufzeitmesung 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 gordnete 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)
Hab in der Wiki eine gute Seite dazu gefunden Ordnungsrelation
Datenspeicherung
Die Daten liegen typischerweise in Form von Arrays oder verketteten Listen vor. Ja 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
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 = 2n
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
C(N)= 2C(N/2)+ N; N>1, C(1)= 0
Sei N= <math>2^n</math>
C(N)= C(<math>2^n</math>)= 2C (<math>2^{n-1}</math>)+ <math>2^n</math>
<=> <math> \cfrac{C(2^n)}{2^n}</math> = <math> \cfrac{2C(2^{n-1})}{2^{n-1}}</math>
= <math> \cfrac{2C(2^{n-2})+2^{n-1}}{2^{n-1}}+1</math>
= <math> \cfrac{2C(2^{n-2})}{2^{n-2}}+1 +1</math>
=...
= n
<=> C(<math>2^n</math>)= <math>2^n</math> * n <=> C= N log<math>_2</math>N
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 stabil, wenn die Vergleiche durch a[j] < a[min] erfolgen, weil dann immer das erste Element mit einem gegebenen Schlüssel als erster nach vorn gebracht wird. Bei Vergleichen a[j] <= a[min] wird hingegen das letzte Element zuerst nach vorn gebracht, somit ist Selection Sort dann nicht stabil.
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 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.
- 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.
Quicksort
- Quicksort wurde in den 60er Jahren von Charles Antony Richard Hoare [1] entwickelt. Es gibt viele Implementierungen von Quicksort, vgl. [2].
- 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). Ausserdem 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 a[i] <= pivot and i < r:
i += 1 # finde von links das erste Element > pivot
while a[j] >= pivot and j > l:
j -= 1 # finde von rechts den ersten Eintrag <= pivot
if i >= j: break # keine weiteren Elemente zum Tauschen => 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
if a[i] > pivot:
a[i], a[r] = a[r], a[i]
return i
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
Wir müssen hier den schlechtesten und den typischen Fall unterscheiden. Der schlechteste Fall tritt ein, wenn das Array bereits sortiert ist. Dann ist das Pivot-Element immer bereits am richtigen Platz, so dass partition(a, l, r) stets den Index i = r zurück. Daher wird das Array niemals in zwei etwa gleichgroße Teile zerlegt. Die Anzahl der Vergleiche ergibt sich als
- <math>C(N) = (N+1) + C(N-1) + C(0)</math>
- <math>C(0) = 0</math>
mit (N+1) Vergleichen in partition(). Durch sukzessives Einsetzen erhalten wir:
- <math>C(N) = (N+1) + (N) + (N-1) + ... + 1 = (N+1) N / 2</math>
In diesem Fall ist Quick Sort also nicht schneller als Selection Sort. Wir beschreiben mögliche Verbesserungen unten. Im typischen Fall (wenn nämlich das Array zufällig sortiert ist) sieht die Situation wesentlich besser aus. Bei zufälliger Sortierung wird jeder Index mit gleicher Wahrscheinlichkeit zur Pivot-Position. 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>
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> Durch Vereinfachen 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(2)}{3} + \sum_{k=3}^N\frac{2}{k+1} </math> Für hinreichend große N kann die Summe sehr genau durch ein Integral approximiert werden. Der konstanten Term kann vernachlässigt werden:
- <math>
\frac{C(N)}{N+1} \approx 2 \sum_{k=3}^{N} \frac{1}{k+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 etwa genauso schnell wie Merge Sort (in der Praxis sogar etwas schneller, da die innere Schleife von Quick Sort etwas einfacher ist).
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
elif r > l:
sortThree(a, l, r)
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 Elementen: Verwende den Median des ersten, mittleren und letzten Elements jedes Teilarrays als Pivot-Element.
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.
