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 16static int *val; /* item values */ 17static int ncmp; /* number of comparisons */ 18static int nsolid; /* number of solid items */ 19static int candidate; /* pivot candidate */ 20static int gas; /* gas value */ 21 22#define freeze(x) (val[(x)] = nsolid++) 23 24static int 25cmp(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 44int 45antiqsort(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