Re: [BK PATCH 1/2] Remove NGROUPS hardlimit (resend w/o qsort)

Horst von Brand
2002-11-15T16:24:09Z

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