Quicksort
Quicksort ist ein allgemeines Sortierverfahren vom Typ
Teile und Herrsche
. Es b eruht auf
dem Zerlegen eines zu sortierenden Feldes in zwei Teile und dem anschlieenden Sortieren der
beiden Teile unabh
angig voneinander. Der Algorithmus hat folgende Gestalt:
void quicksort (int A[], int l, int r)
{
if(l >= r) return;
int i = l;
int j = r+1;
int v = A[l];
for (;;)
{
while(A[++i] < v && i < r);
while(A[--j] > v);
if(i >= j) {
swap(A, l, j);
break;
}
swap(A, i, j);
}
quicksort(A, l, j-1);
quicksort(A, j+1, r);
}
Die Parameter
l
und
r
b egrenzen das Teilfeld innerhalb des urspr
unglichen Feldes, welches zu
sortieren ist; der Aufruf
quicksort(A, 0, A.size()-1)
sortiert das gesamte Feld.
Das entscheidene Element der Metho de ist der Programmco de innerhalb der unendlichSchleife
for(;;)
, der das Feld so umordnet, da die folgenden Bedingungen erf
ullt sind:
i. F
ur ein b eliebiges
j
b endet sich das Element
A[j]
an seinem endg
ultigen Platz im Feld.
ii. Alle Elemente
A[l],
:::
,A[j-1]
sind kleiner o der gleich
A[j]
.
iii. Alle Elemente
A[j+1],
:::
,A[r]
sind gr
oer o der gleich
A[j]
.
Im ersten Schritt wird das zerlegende Element
v = A[l]
ausgew
ahlt, das in seine endg
ultige
Position gebracht werden soll. Jetzt b eginnt die Suche von links, bis ein Element gefunden
wurde, welches gr
oer als
v
ist, anschlieend startet die Suche von rechts, bis ein Element ge-
funden wurde, das kleiner als
v
ist.
Hab en sich die Zeiger
i
und
j
no ch nicht getroen, dann werden die Elemente
A[i]
und
A[j]
miteinander vertauscht, andernfalls wird durch einen weiteren Austausch die Beding-
ung i. sichergestellt und die unendlichSchleife durch ein
break
verlassen.
Im folgenden wird die Funktion f
ur das linkeTeilfeld und danachf
ur das rechte Teilfeld rekursiv
aufgerufen. Am Ende ist das Feld aufsteigend sortiert.
1
