/* quicksort() has a list of sorting problems: x,xlen; stack[0].x,stack[0].xlen; stack[1].x,stack[1].xlen; and so on through stack[stacklen-1].x,stack[stacklen-1].xlen. The sorting problem x,xlen is to put x[0],x[1],...,x[xlen-1] into order. All of these variables are separate: x in smallest; x in largest; x in quicksort; x in main; stack[0].x in quicksort; stack[1].x in quicksort; etc. */ #include #include struct doublechunk { double *x; int xlen; } ; double smallest(double *x,int xlen) { int i; double result; if (xlen < 1) return 0; result = x[0]; for (i = 1;i < xlen;++i) if (x[i] < result) result = x[i]; return result; } double largest(double *x,int xlen) { int i; double result; if (xlen < 1) return 0; result = x[0]; for (i = 1;i < xlen;++i) if (x[i] > result) result = x[i]; return result; } void quicksort(double *x,int xlen) { struct doublechunk stack[100]; int stacklen = 0; int i; int j; double split; double t; for (;;) { if (xlen < 2) { if (!stacklen) return; --stacklen; x = stack[stacklen].x; xlen = stack[stacklen].xlen; continue; } split = smallest(x,xlen); split += 0.5 * (largest(x,xlen) - split); i = 0; j = xlen; for (;;) { if (i == j) break; if (x[i] <= split) { ++i; continue; } if (x[j - 1] > split) { --j; continue; } t = x[i]; x[i] = x[j - 1]; x[j - 1] = t; } while (i && (x[i - 1] == split)) --i; if (stacklen == 100) return; /* out of space! this will never happen */ if (i > xlen - j) { stack[stacklen].x = x; stack[stacklen].xlen = i; x += j; xlen -= j; } else { stack[stacklen].x = x + j; stack[stacklen].xlen = xlen - j; xlen = i; } ++stacklen; } } int main(void) { 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; } quicksort(x,xlen); for (i = 0;i < xlen;++i) printf("%f\n",x[i]); return 0; }