/* Compare to qsort1. Can you rewrite smallest() and largest() to eliminate the i variable? */ #include #include struct doublechunk { double *x; int xlen; } ; double smallest(struct doublechunk p) { int i; double result; if (p.xlen < 1) return 0; result = p.x[0]; for (i = 1;i < p.xlen;++i) if (p.x[i] < result) result = p.x[i]; return result; } double largest(struct doublechunk p) { int i; double result; if (p.xlen < 1) return 0; result = p.x[0]; for (i = 1;i < p.xlen;++i) if (p.x[i] > result) result = p.x[i]; return result; } void quicksort(struct doublechunk p) { struct doublechunk stack[100]; int stacklen = 0; int i; int j; double split; double t; for (;;) { if (p.xlen < 2) { if (!stacklen) return; p = stack[--stacklen]; continue; } split = smallest(p); split += 0.5 * (largest(p) - split); i = 0; j = p.xlen; for (;;) { if (i == j) break; if (p.x[i] <= split) { ++i; continue; } if (p.x[j - 1] > split) { --j; continue; } t = p.x[i]; p.x[i] = p.x[j - 1]; p.x[j - 1] = t; } while (i && (p.x[i - 1] == split)) --i; if (stacklen == 100) return; /* out of space! this will never happen */ if (i > p.xlen - j) { stack[stacklen].x = p.x; stack[stacklen].xlen = i; p.x += j; p.xlen -= j; } else { stack[stacklen].x = p.x + j; stack[stacklen].xlen = p.xlen - j; p.xlen = i; } ++stacklen; } } int main(void) { struct doublechunk p; double *x = 0; int xspace = 0; int xlen = 0; int i; double r; while (scanf("%lf",&r) == 1) { if (xlen == xspace) if (!(x = realloc(x,(xspace = xspace * 2 + 1) * sizeof(double)))) { fprintf(stderr,"out of memory\n"); return 111; } x[xlen++] = r; } p.x = x; p.xlen = xlen; quicksort(p); for (i = 0;i < xlen;++i) printf("%f\n",x[i]); return 0; }