Here are semi-templated versions of quicksort and heapsort, just for
completeness. The quicksort uses the median of three.
Chuck
void quicksort0<typename>(<typename> *pl, <typename> *pr)
{
<typename> vp, SWAP_temp;
<typename> *stack[100], **sptr = stack, *pm, *pi, *pj, *pt;
for(;;) {
while ((pr - pl) > 15) {
/* quicksort partition */
pm = pl + ((pr - pl) >> 1);
if (<lessthan>(*pm,*pl)) SWAP(*pm,*pl);
if (<lessthan>(*pr,*pm)) SWAP(*pr,*pm);
if (<lessthan>(*pm,*pl)) SWAP(*pm,*pl);
vp = *pm;
pi = pl;
pj = pr - 1;
SWAP(*pm,*pj);
for(;;) {
do ++pi; while (<lessthan>(*pi,vp));
do --pj; while (<lessthan>(vp,*pj));
if (pi >= pj) break;
SWAP(*pi,*pj);
}
SWAP(*pi,*(pr-1));
/* push largest partition on stack */
if (pi - pl < pr - pi) {
*sptr++ = pi + 1;
*sptr++ = pr;
pr = pi - 1;
}else{
*sptr++ = pl;
*sptr++ = pi - 1;
pl = pi + 1;
}
}
/* insertion sort */
for(pi = pl + 1; pi <= pr; ++pi) {
vp = *pi;
for(pj = pi, pt = pi - 1; pj > pl && <lessthan>(vp,
*pt);) {
*pj-- = *pt--;
}
*pj = vp;
}
if (sptr == stack) break;
pr = *(--sptr);
pl = *(--sptr);
}
}
void heapsort0<typename>(<typename> *a, long n)
{
<typename> tmp;
long i,j,l;
/* The array needs to be offset by one for heapsort indexing */
a -= 1;
for (l = n>>1; l > 0; --l) {
tmp = a[l];
for (i = l, j = l<<1; j <= n;) {
if (j < n && <lessthan>(a[j], a[j+1]))
j += 1;
if (<lessthan>(tmp, a[j])) {
a[i] = a[j];
i = j;
j += j;
}else
break;
}
a[i] = tmp;
}
for (; n > 1;) {
tmp = a[n];
a[n] = a[1];
n -= 1;
for (i = 1, j = 2; j <= n;) {
if (j < n && <lessthan>(a[j], a[j+1]))
j++;
if (<lessthan>(tmp, a[j])) {
a[i] = a[j];
i = j;
j += j;
}else
break;
}
a[i] = tmp;
}
}
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
