1 /* 2 * A Killer Adversary for Quicksort 3 * M. D. MCILROY 4 * http://www.cs.dartmouth.edu/~doug/mdmspe.pdf 5 * 6 * For comparison: 7 * Bentley & McIlroy: 4096 items, 1645585 compares 8 * random pivot: 4096 items, 8388649 compares 9 * introsort: 4096 items, 151580 compares 10 * heapsort: 4096 items, 48233 compares 11 */ 12 13 #include <stdio.h> 14 #include <stdlib.h> 15 16 static int *val; /* item values */ 17 static int ncmp; /* number of comparisons */ 18 static int nsolid; /* number of solid items */ 19 static int candidate; /* pivot candidate */ 20 static int gas; /* gas value */ 21 22 #define freeze(x) (val[(x)] = nsolid++) 23 24 static int 25 cmp(const void *px, const void *py) 26 { 27 const int x = *(const int *)px; 28 const int y = *(const int *)py; 29 30 ncmp++; 31 if (val[x] == gas && val[y] == gas) { 32 if (x == candidate) 33 freeze(x); 34 else 35 freeze(y); 36 } 37 if (val[x] == gas) 38 candidate = x; 39 else if (val[y] == gas) 40 candidate = y; 41 return val[x] > val[y] ? 1 : val[x] < val[y] ? -1 : 0; 42 } 43 44 int 45 antiqsort(int n, int *a, int *ptr) 46 { 47 int i; 48 49 val = a; 50 gas = n - 1; 51 nsolid = ncmp = candidate = 0; 52 for (i = 0; i < n; i++) { 53 ptr[i] = i; 54 val[i] = gas; 55 } 56 qsort(ptr, n, sizeof(*ptr), cmp); 57 return ncmp; 58 } 59