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.
was macht das return in der void methode? exch scheint die werte zu vertauchen mehr check ich nicht.
Code:
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);
}
Zuletzt bearbeitet: