/* Copyright 1998, M. Douglas McIlroy Permission is granted to use or copy with this notice attached. Aqsort is an antiquicksort. It will drive any qsort implementation based on quicksort into quadratic behavior, provided the imlementation has these properties: 1. The implementation is single-threaded. 2. The pivot-choosing phase uses O(1) comparisons. 3. Partitioning is a contiguous phase of n-O(1) comparisons, all against the same pivot value. 4. No comparisons are made between items not found in the array. Comparisons may, however, involve copies of those items. Method Values being sorted are dichotomized into "solid" values that are known and fixed, and "gas" values that are unknown but distinct and larger than solid values. Initially all values are gas. Comparisons work as follows: Solid-solid. Compare by value. Solid-gas. Solid compares low. Gas-gas. Solidify one of the operands, with a value greater than any previously solidified value. Compare afresh. During partitioning, the gas values that remain after pivot-choosing will compare high, provided the pivot is solid. Then qsort will go quadratic. To force the pivot to be solid, a heuristic test identifies pivot candidates to be solidified in gas-gas comparisons. A pivot candidate is the gas item that most recently survived a comparison. This heuristic assures that the pivot gets solidified at or before the second gas-gas comparison during the partitioning phase, so that n-O(1) gas values remain. To allow for copying, we must be able to identify an operand even if it was copied from an item that has since been solidified. Hence we keep the data in fixed locations and sort pointers to them. Then qsort can move or copy the pointers at will without disturbing the underlying data. int aqsort(int n, int *a); returns the count of comparisons qsort used in sorting an array of n items and fills in array a with the permutation of 0..n-1 that achieved the count. */ #include #include int *val; /* array, solidified on the fly */ int ncmp; /* number of comparisons */ int nsolid; /* number of solid items */ int candidate; /* pivot candidate */ int gas; /* gas value = highest sorted value */ #define freeze(x) val[x] = nsolid++ int cmp(const void *px, const void *py) /* per C standard */ { const int x = *(const int*)px; const int y = *(const int*)py; ncmp++; if(val[x]==gas && val[y]==gas) if(x == candidate) freeze(x); else freeze(y); if(val[x] == gas) candidate = x; else if(val[y] == gas) candidate = y; return val[x] - val[y]; } int aqsort(int n, int *a) { int i; int *ptr = malloc(n*sizeof(*ptr)); val = a; gas = n-1; nsolid = ncmp = candidate = 0; for(i=0; i #include int pflag; main(int argc, char **argv) { int n, i; int *b; if(argc>1 && strcmp(argv[1],"-p") == 0) { pflag++; argc--; argv++; } if(argc != 2) { fprintf(stderr,"usage: aqsort [-p] n\n"); exit(1); } n = atoi(argv[1]); b = malloc(n*sizeof(int)); if(b == 0) { fprintf(stderr,"aqsort: out of space\n"); exit(1); } i = aqsort(n, b); printf("n=%d count=%d\n", n, i); if(pflag) for(i=0; i