14 static int comp(struct rec *r1, struct rec *r2)
19 static int comp2(struct rec *r1, struct rec *r2)
24 void shuffle(struct rec *d, int n)
31 qsort(d, n, sizeof(*d), comp);
34 int count(struct rec *d, int n, int x)
39 if (d[i].d == x) ret++;
44 static double avg(struct rec *d, int n, int loops)
49 for (i=0;i<loops;i++) {
51 sum += abs(n/2 - count(d, n, 1));
56 static double countr(struct rec *d, int n, int loops, int r)
61 for (i=0;i<loops;i++) {
63 if (count(d, n, 1) == r) sum++;
65 return sum/(1.*loops);
69 static double sqr(double x)
74 static double fact(int n)
83 static double binomial(int n, int k)
85 return fact(n) / (fact(k) * fact(n-k));
88 static double P0(int n)
90 return sqr(fact(n/2)) / fact(n);
93 static double P1(int n)
95 return P0(n) * (n/2) * (n/2);
98 static double P2(int n)
100 return P0(n) * (n/2) * (n/2 - 1)/2 * binomial(n/2, 2);
103 static double Pn(int n, int r)
105 return sqr(binomial(n/2, r)) * sqr(fact(n/2)) / fact(n);
108 static double En(int n)
110 return (n/2) * (sqr(fact(n/2))/fact(n)) * binomial(n-1, n/2-1);
119 ---------------------
123 > 4*sum(p*(n/2 - i),i=0..n/2);
126 (n!) binomial(n, 1 + 1/2 n) (1 + 1/2 n)
127 2 ------------------------------------------
131 This is the expected number of elements in the wrong cell after the
132 hypercube phase of a 4 way internal sort.
137 /* take n random elements. Sample k of those elements. How far is the median
138 of the n elements from the median of the k elements? Answer in terms
139 of the k elements (so the answer is at most k/2) */
140 static int median_deviation(int n, int k)
147 srandom(getpid() ^ time(NULL));
149 d = (struct rec *)malloc(sizeof(d[0])*n);
156 for (j=0;j<loops;j++) {
159 qsort(d, k, sizeof(*d), comp2);
161 sum += abs(n/2 - d[k/2].d);
171 int main(int argc, char *argv[])
175 int N = atoi(argv[1]);
176 int k = atoi(argv[2]);
178 loops = atoi(argv[3]);
180 printf("median_deviation(N, k) = %g\n", median_deviation(N, k));