swlpc Git

95 lines (88 with data), 1.9 kB

/*
 * Quick 'n nasty heap sort routine.
 * Does an in-place sort on an array.
 * Sorts about 270 elements before eval-costing - this
 * could probably be increased.
 * will be fixed soon to work on key, value pairs.
 * Gandalf, '92.
 *
 * Call sort(arr, eltsize, compelt).
 * Sorts arr in place, also returns the array.
 * Eltsize is the number of array items per element.
 * compelt is the offset of the elt to compare within the array.
 */

reset() {
    return 0;
    }

#define Lchild(x) (x + x + eltsize)
#define Parent(x) ((x - eltsize) / 2)
#define LRchild(x) (x + eltsize)

array sort(array a, int eltsize, int compelt) {
    int N = sizeof(a);
    if (eltsize < 1)
	eltsize = 1;
    if (N % eltsize)
	throw("Sort: Array size not a multiple of element size");
    if (compelt < 0)
	throw("Sort: Comparison element offset negative");
    if (compelt >= eltsize)
	throw("Sort: Comparison element offset too large");
    int i = 0;
/*
 * Build a heap by successive upward sifts.
 */
    while ((++i) < N) {
	int j = i;
	int k = i;
	int ai = a[i];
	do {
	    j = Parent(k);
	    int aj = a[j];
	    if (ai > aj) {
		a[k] = aj;
		}
	    else {
		a[k] = ai;
		j = 0;
		ai = a[0];
		}
	    k = j;
	    }
		while (j > 0);
	    a[j] = ai;
	}
/*
 * Sort the array with successive filtering ops.
 */
    while (--N > 0) {
	int tmp = a[N]; a[N] = a[0]; a[0] = tmp;
	tmp = 0; /* N is now one element past the array again */
        int c = Lchild(tmp);
	while (c < N) {
	    if ((c < (N-1)) && (a[c+1] > a[c]))
		c++;
	    if (a[c] > a[tmp]) {
		int t2 = a[tmp]; a[tmp] = a[c]; a[c] = t2;
		tmp = c;
		c = Lchild(c);
		}
	    else
		c = N;
	}
    }

    return a;
}

show (array a) {
    int x = 0;
    while (x < sizeof(a))
	write(" " + a[x++]);
    write("\n");
}

test(int x) {
    array a = allocate(x);
    while (--x >= 0)
	a[x] = random(100);
    show(a);
    x = sizeof(a = sort(a));
    show(a);
}