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