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