Quicksort
QuickSort (von engl. quick – schnell, to sort – sortieren) ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche (engl. Divide and conquer) arbeitet. Er wurde 1962 von C. Antony R. Hoare in seiner Grundform erfunden und seitdem von vielen Forschern weiterentwickelt. Der Algorithmus hat den Vorteil, dass er über eine sehr kurze innere Schleife verfügt (was die Ausführungsgeschwindigkeit stark erhöht) und ohne zusätzlichen Speicherplatz auskommt (abgesehen von dem für die Rekursion zusätzlichen benötigten Platz auf dem Aufruf-Stack).
Prinzip
QuickSort wählt ein Element aus der zu sortierenden Liste aus (Pivotelement) und zerlegt die Liste in zwei Teilllisten, eine untere, die alle Elemente kleiner und eine obere, die alle Elemente gleich oder größer dem Pivotelement enthält. Dazu wird zunächst ein Element von unten gesucht, das größer als (oder gleichgroß wie) das Pivotelement und damit für die untere Liste zu groß ist. Entsprechend wird von oben ein kleineres Element als das Pivotelement gesucht. Die beiden Elemente werden dann vertauscht und landen damit in der jeweils richtigen Liste. Der Vorgang wird fortgesetzt, bis sich die untere und obere Suche treffen. Damit sind die oben erwähnten Teillisten in einem einzigen Durchlauf entstanden. Suche und Vertauschung können in-place durchgeführt werden.
Die noch unsortierten Teillisten werden über denselben Algorithmus in noch kleinere Teillisten zerlegt (z. B. mittels Rekursion) und, sobald nur noch Listen mit je einem Element vorhanden sind, wieder zusammengesetzt. Die Sortierung ist damit abgeschlossen.
Laufzeit
Der Algorithmus wird meist so implementiert, dass als Pivotelement das Element in der Mitte oder am Ende der (Teil-)Liste gewählt wird.
Im worst case (schlechtesten Fall) wird das Pivotelement stets so gewählt, dass es das größte oder das kleinste Element der Liste ist. Dies ist etwa der Fall, wenn als Pivotelement stets das Element am Ende der Liste gewählt wird und die zu sortierende Liste bereits sortiert vorliegt.
Die von QuickSort benötigte Rechenzeit liegt im worst case in der Komplexitätsklasse O(n²), im Mittel aber in O(n·log(n)).
Ein Ansatz, um worst-case-Laufzeiten zu verhindern, ist, als Pivotelement ein zufällig bestimmtes Element zu wählen. Bei diesem randomisierten Quicksort ist die Wahrscheinlichkeit, dass das Pivotelement in jedem Teilungsschritt so gewählt wird, dass sich die worst case-Laufzeit ergibt, extrem gering, so dass man praktisch von einer Komplexität von O(n·log(n)) ausgehen kann. Eine andere Möglichkeit ist die Verwendung des Medians von z.B. drei zufällig gewählten Elementen. Durch geschickte Wahl des Pivotelementes kann man aber nur das mittlere schlechteste Verhalten verbessern. Vollständig verhindern kann man das Eintreten des Worst Cases jedoch nicht.
In der Praxis wird der Algorithmus trotz des möglichen Auftretens des schlechtesten Falles verwendet. Er ist heute für ein breites Spektrum von praktischen Anwendungen die bevorzugte Sortiermethode, weil er schnell ist und, sofern Rekursion zur Verfügung steht, einfach zu implementieren ist. In vielen Standard-Bibliotheken ist er bereits vorhanden.
Quicksort setzt jedoch voraus, dass effizient (d.h. mit Aufwand O(1)) über einen Index auf die Elemente zugegriffen werden kann. Dies ist jedoch meist nur bei Arrays der Fall. Für verkettete Listen sind andere Sortieralgorithmen meist effektiver, wie etwa adaptiertes 2-Phasen-2-Band-Mischen oder Mergesort. Andere dynamische Datenstrukturen wie balancierte Bäume (B-Bäume, AVL-Bäume oder 2-3-4-Bäume, letztere meist effektiv implementiert als Rot-Schwarz-Baum) verteilen die Kosten des Sortierens auf die Einfügeoperationen, so dass nachträgliches Sortieren nicht notwendig ist.
Implementierung
Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus. Dabei ist daten das zu sortierende Feld.
funktion quicksort(links, rechts)
falls rechts > links
teiler := teile(links, rechts)
quicksort(links, teiler-1)
quicksort(teiler+1, rechts)
Die Funktion teile muss dabei das Feld so teilen, dass sich das Pivotelement an seiner endgültigen Position befindet und alle kleineren Elemente davor stehen, während alle größeren danach kommen, zum Beispiel durch
funktion teile(links, rechts)
index := links
von zeiger := links bis rechts-1
falls daten[zeiger] <= daten[rechts]
tausche(index, zeiger)
index := index + 1
tausche(index, rechts)
antworte index
funktion tausche(a, b) temp := daten[a] daten[a] := daten[b] daten[b] := temp
Eine abgewandelte Version der Funktion teile ist die folgende:
funktion teile(links, rechts)
i := links-1
j := rechts
pivot := rechts
fürimmer
// Suche von links ein Element, das >= daten[pivot] ist
i := i + 1
solange daten[i] < daten[pivot]
i := i + 1
// Suche von rechts ein Element, das < daten[pivot] ist
j := j - 1
solange (daten[pivot] < daten[j]) und (j > links)
j := j - 1
// Abbruch, wenn sich i und j "kreuzen"
falls i >= j
abbruch
// vertausche zwei unpassende Elemente
tausche(i, j)
endefürimmer
// setze Pivot an die richtige Stelle und gib seine Position zurück
tausche(i, pivot)
antworte i;
Beispiel teile(l,r)
1. Variante
| 4 | 9 | 3 | 3 | 8 | 2 | 7 | 6 | 5 | Der Algorithmus startet mit einer Liste von 9 Elementen. Das rechte Element (5) wird als Pivotelement ausgewählt. Im folgenden werden alle größeren Elemente mit der Web-Farbe Honeydew und alle kleineren Elemente mit der Web-Farbe LemonChiffon hinterlegt. Das Indexelement wird rot hinterlegt und der Zeiger wird mit einem ↑ dargestellt. |
| 4↑ | 9 | 3 | 3 | 8 | 2 | 7 | 6 | 5 | Am Anfang steht der rote Index und der Zeiger auf dem ersten Element. Im weiteren Algorithmus sind immer alle Elemente links vom Index kleiner gleich dem Pivotelement. Das Element unter dem Zeiger (4) wird mit dem Pivotelement (5) verglichen. |
| 4↑ | 9 | 3 | 3 | 8 | 2 | 7 | 6 | 5 | Da aus dem Vergleich im vorigen Schritt hervorgeht, dass die 4 kleiner gleich dem Pivotelement (5) ist, wandert der rote Index zum zweiten Element.¹ |
| 4 | 9↑ | 3 | 3 | 8 | 2 | 7 | 6 | 5 | Der Zeiger wandert zum zweiten Element (9) und vergleicht dieses mit dem Pivotelement (5). |
| 4 | 9 | 3↑ | 3 | 8 | 2 | 7 | 6 | 5 | Der Zeiger wandert zum dritten Element (3) und vergleicht dieses mit dem Pivotelement (5). |
| 4 | 3 | 9↑ | 3 | 8 | 2 | 7 | 6 | 5 | Da das dritte Element kleiner gleich ist, wird dieses mit dem Indexelement vertauscht und der Index wandert zum dritten Element. |
| 4 | 3 | 9 | 3↑ | 8 | 2 | 7 | 6 | 5 | Der Zeiger wandert zum vierten Element (3), dieses ist kleiner gleich dem Pivotelement. |
| 4 | 3 | 3 | 9↑ | 8 | 2 | 7 | 6 | 5 | Elemententausch und Indexwanderung. |
| 4 | 3 | 3 | 9 | 8↑ | 2 | 7 | 6 | 5 | Der Zeiger wandert zum nächsten Element (8). |
| 4 | 3 | 3 | 9 | 8 | 2↑ | 7 | 6 | 5 | Der Zeiger wandert weiter (2). Dieses Element ist kleiner gleich dem Pivotelement. |
| 4 | 3 | 3 | 2 | 8 | 9↑ | 7 | 6 | 5 | Tausch und Indexwanderung. |
| 4 | 3 | 3 | 2 | 8 | 9 | 7↑ | 6 | 5 | Der Zeiger wandert. |
| 4 | 3 | 3 | 2 | 8 | 9 | 7 | 6↑ | 5 | Der Zeiger wandert. |
| 4 | 3 | 3 | 2 | 5 | 9 | 7 | 6↑ | 8 | Da der Zeiger am Ende angekommen ist, wird das Pivotelement mit dem Indexelement getauscht. Der Index zeigt nun auf diejenige Position, welche die Liste in eine linke, mit kleineren Elementen besetzte Liste, und in eine rechte, mit größeren Elementen besetzte Liste teilt. |
¹ Eigentlich wird das erste Element mit sich selbst vertauscht, da Zeiger und Index auf dem gleichen Element liegen. Dies hat aber keine sichtbare Auswirkung.
2. Variante
Varianten
Die Effizienz von QuickSort liegt darin, dass es Elemente aus großer Distanz miteinander vertauscht. Je kürzer die zu sortierende Liste wird, desto ineffizienter arbeitet QuickSort, da es sich einer Komplexität von O(n²) nähert. Die von QuickSort in Teillisten zerlegte Liste hat jedoch die Eigenschaft, dass der Abstand zwischen einem Element und seiner sortierten Position nach oben beschränkt ist. Eine solche Liste sortiert Insertionsort in linearer Zeit, so dass häufig in der Implementierung unterhalb einer definierten Teillistenlänge der QuickSort abgebrochen wird, um mit Insertionsort weiterzusortieren.
Siehe auch: IntroSort
Implementierungen in diversen Programmiersprachen
quicksort [] = []
quicksort (x:xs) = quicksort [y | y <- xs, y < x] ++ [x] ++ quicksort [y | y <- xs, y >= x]
sub qsort {
@_ or return ();
my $p = shift;
(qsort(grep $_ < $p, @_), $p, qsort(grep $_ >= $p, @_));
}
multi quicksort () { () }
multi quicksort (*$x, *@xs) {
my @pre = @xs.grep:{ $_ < $x };
my @post = @xs.grep:{ $_ >= $x };
(@pre.quicksort, $x, @post.quicksort);
}
#s ist eine Liste
def quicksort(s):
if len(s) <= 1:
return s
else:
return quicksort([x for x in s[1:] if x < s[0]]) + [s[0]] + quicksort([y for y in s[1:] if y >= s[0]])
import java.util.Comparator;
import java.util.Random;
public class Quicksort {
public static final Random RND = new Random();
private void swap(Object[] array, int i, int j) {
Object tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
private int partition(Object[] array, int begin, int end, Comparator cmp) {
int index = begin + RND.nextInt(end - begin + 1);
Object pivot = array[index];
swap(array, index, end);
for (int i = index = begin; i < end; ++ i) {
if (cmp.compare(array[i], pivot) <= 0) {
swap(array, index++, i);
} }
swap(array, index, end);
return (index);
}
private void qsort(Object[] array, int begin, int end, Comparator cmp) {
if (end > begin) {
int index = partition(array, begin, end, cmp);
qsort(array, begin, index - 1, cmp);
qsort(array, index + 1, end, cmp);
}
}
public void sort(Object[] array, Comparator cmp) {
qsort(array, 0, array.length - 1, cmp);
} }
procedure quicksort(var a:array of integer;l,r:integer);
var lpos,rpos,tmp,pivot:integer;
begin
pivot:=a[(l+r) div 2];
lpos:=l;
rpos:=r;
while lpos<=rpos do
begin
while a[lpos]<pivot do inc(lpos);
while a[rpos]>pivot do dec(rpos);
if lpos<=rpos then
begin
tmp:=a[lpos];
a[lpos]:=a[rpos];
a[rpos]:=tmp;
inc(lpos);
dec(rpos);
end;
end;
if l<rpos then quicksort(a,l,rpos);
if lpos<r then quicksort(a,lpos,r);
end;
Public Sub QuickSort(ByVal LB As Long, ByVal UB As Long)
Dim P1 as Long, P2 As Long
Dim Ref as String, TEMP As String
P1 = LB
P2 = UB
Ref = Feld((P1 + P2) / 2)
Do
Do While (Feld(P1) < Ref)
P1 = P1 + 1
Loop
Do While (Feld(P2) > Ref)
P2 = P2 - 1
Loop
If P1 <= P2 Then
TEMP = Feld(P1)
Feld(P1) = Feld(P2)
Feld(P2) = TEMP
P1 = P1 + 1
P2 = P2 - 1
End If
Loop Until (P1 > P2)
If LB < P2 Then Call QuickSort(LB, P2)
If P1 < UB Then Call QuickSort(P1, UB)
End Sub
void sort_quick(int a[], int al, int ar) {
int links=al, rechts=ar, pivo=a[(al+ar)/2], tmp;
do {
while(a[links]<pivo) links++;
while(a[rechts]>pivo) rechts--;
if (links <= rechts) {
tmp=a[links];
a[links]=a[rechts];
a[rechts]=tmp;
links++;
rechts--;
}
} while(links<rechts);
if (al < rechts) sort_quick(a, al, rechts);
if (links < ar) sort_quick(a, links, ar);
}
def quicksort( array )
if array.size <= 1
array
else
ls, rest = array.partition { |i| i < array[0] }
rs, rest = rest.partition { |i| i > array[0] }
quicksort( ls ) + rest + quicksort( rs )
end
end
Weitere Sortierverfahren
- Shellsort
- Heapsort (siehe auch Heap)
- Mergesort
- Bubblesort
- Insertionsort
- Selectionsort
Siehe auch: Sortierverfahren
Literatur
- Robert Sedgewick: Algorithmen. Pearson Studium 2002 ISBN 3827370329
- Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein: Introduction to Algorithms (Second Edition), ISBN 0262032937 – ein Standardwerk zu Algorithmen
Weblinks
- Vollständiger Quicksort-Artikel auf www.linux-related.de
- Überblick über mögliche Geschwindigkeitsoptimierungen
- Verstehen durch Schritt-für-Schritt Ausprobieren
- VisuSort Framework - Visualisierung diverser Sortieralgorithmen (Windows)
- Pseudocode zu Quicksort und seinen Varianten
- Robert F. Stärk: Animated Sorting Algorithms – Java-Beispiele
- Beispiel zum Teilen der Daten
- QuickSort Animation