/* Compare to qsort4. Notice the recursion in quicksort(). */ #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 q; int i; int j; double split; double t; while (p.xlen >= 2) { 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; q = p; if (i > p.xlen - j) { q.x += j; q.xlen -= j; p.xlen = i; } else { p.x += j; p.xlen -= j; q.xlen = i; } quicksort(q); } } 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; }