/* A much faster sorting program. Try creating a rand.out file with 10000 random numbers. Do this as a programmer, not a user: first write a rand program that reads n and does printf("%d\n",rand()) n times, using the standard library function rand(); then type rand > rand.out 10000 to create the rand.out file. Now feed rand.out to dyn6 and dyn7, and see how long they take: time dyn6 < rand.out > dyn6.out time dyn7 < rand.out > dyn7.out Compare the output files to make sure dyn6 and dyn7 did the same job: cmp dyn6.out dyn7.out If the output files are identical, cmp won't print anything. Finally, remove the random files: rm rand.out dyn6.out dyn7.out The sorting algorithm in dyn7.c is called ``heapsort.'' It's explained in subsequent MCS courses. */ #include #include int doublearray_append(double **a,int *aspace,int *alen,double d) { if (*alen == *aspace) { int yspace = *aspace * 2 + 1; double *y = (double *) realloc(*a,yspace * sizeof(double)); if (!y) return 0; *a = y; *aspace = yspace; } (*a)[*alen] = d; ++*alen; return 1; } /* sort a[0], a[1], ..., a[n-1] */ void sort(double *a,int n) { double t; int i = n; int p; int q; --a; /* now want to sort a[1], a[2], ..., a[n] */ while (n > 1) { if (i > 1) t = a[--i]; else { t = a[n]; a[n--] = a[1]; } q = i; while ((p = q * 2) < n) { if (a[p + 1] >= a[p]) ++p; a[q] = a[p]; q = p; } if (p == n) { a[q] = a[p]; q = p; } while ((q > i) && (t > a[p = q / 2])) { a[q] = a[p]; q = p; } a[q] = t; } } int main(void) { double *x = 0; int xspace = 0; int xlen = 0; double d; int i; while (scanf("%lf",&d) == 1) if (!doublearray_append(&x,&xspace,&xlen,d)) { printf("out of memory\n"); exit(1); } sort(x,xlen); for (i = 0;i < xlen;++i) printf("%f\n",x[i]); return 0; }