Messages in this thread | | | Subject | Re: [BK PATCH 1/2] Remove NGROUPS hardlimit (resend w/o qsort) | Date | Fri, 15 Nov 2002 13:30:51 -0300 | From | Horst von Brand <> |
| |
Timothy Hockin <th122948@scl2.sfbay.sun.com> said:
[...]
> +/* a simple shell-metzner sort */ > +static void groupsort(gid_t *grouplist, int gidsetsize) > +{ > + int right, left, cur, max, stride; > + > + stride = gidsetsize / 2;
This guarantees bad performance for certain gidgetsizes... customary wisdom (at least, Knuth sayeth so) is to go:
for(stride = 1; stride < gidgetsize; stride = 3 * stride + 1) ; do { stride /= 3; ... } while (stride > 1) {
> + while (stride) { > + max = gidsetsize - stride; > + > + for (left = 0; left < max; left++) { > + cur = left; > + while (cur >= 0) { > + right = cur + stride; > + if (grouplist[right] < grouplist[cur]) { > + gid_t tmp = grouplist[cur]; > + grouplist[cur] = grouplist[right]; > + grouplist[right] = tmp; > + cur -= stride; > + } else { > + break; > + } > + }
You should work by stuffing the new element in a temporary variable, and just shift the greater ones up, then stuff the one in
My version of shellsort (h is stride, n is size) goes:
/* * shellsort.c: Shell sort */
#include "sort.h"
void sort(double a[], int n)
{ int i, j, h; double tmp;
for(h = 1; h < n; h = 3 * h + 1) ;
do { h /= 3; for(i = h; i < n; i++) { tmp = a[i]; for(j = i - h; j >= 0 && tmp < a[j]; j -= h) a[j + h] = a[j]; a[j + h] = tmp; } } while(h > 1); }
This gets around bad h (stride) values, and does just a bit more than 1 assignment per element moved in the inner loop (you do 3). Plus it is shorter ;-) -- Dr. Horst H. von Brand User #22616 counter.li.org Departamento de Informatica Fono: +56 32 654431 Universidad Tecnica Federico Santa Maria +56 32 654239 Casilla 110-V, Valparaiso, Chile Fax: +56 32 797513 - 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/
| |