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
cmp(const void * px,const void * py)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
antiqsort(int n,int * a,int * ptr)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