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