Quicksort aus den Sedgewick

[maxhd2]

ich muss den "Quicksort with three-way partitioning" aus den sedgewick verstehn, leider ist da nur ein pseudocode-ausschnitt dabei und eine vernüftige erklärung zu der variante such ich auch vergebens.
was macht das return in der void methode? exch scheint die werte zu vertauchen mehr check ich nicht.

static void quicksort(ITEM a[], int l, int r)
{
if (r <= l) return;
ITEM v = a[r];
int i = l-1, j = r, p = l-1, q = r, k;
for (;;)
{
   while (less(a[++i], v)) ;
   while (less(v, a[--j])) if (j == l) break;
   if (i >= j) break;
   exch(a, i, j);
   if (equal(a[i], v)) { p++; exch(a, p, i); }
   if (equal(v, a[j])) { q--; exch(a, q, j); }
}
exch(a, i, r); j = i-1; i = i+1;
for (k = l ; k <= p; k++,j--) exch(a, k, j);
for (k = r-1; k >= q; k--,i++) exch(a, k, i);
quicksort(a, l, j);
quicksort(a, i, r);
}

 

[flashray]

Hallo Max,

das return beendet vorzeitig die Methode. D.h. ist r kleiner gleich l wird der Rest des Codes nicht mehr ausgeführt. Das ist die Abbruchbedingung. l steht für linken zeigerindex und r für rechten zeigerindex. Wenn r gleich l ist, heißt das der rechte und linke Zeiger befinden sich auf der gleichen Position, bei kleiner befindet sich der rechte Zeiger links vom linken Zeiger, daraufhin wird die Methode mit return beendet.

Genau exch steht für exchange als vertauschen, wobei hier die Implementierung fehlt.

Für mehr Info schau mal hier:
http://de.wikipedia.org/wiki/QuickSort

Vg Erdal