Messages in this thread | | | Subject | Re: [patch 1/13] Qsort | From | Charles R Harris <> | Date | Sun, 23 Jan 2005 20:44:33 -0700 |
| |
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 majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |