\datethis @* Primitive sorting networks at random. This program is a quick-and-dirty implementation of the random process studied in exercise 5.3.4--40: Start with the permutation \$n\,\ldots\,2\,1\$ and randomly interchange adjacent elements that are out of order, until reaching \$1\,2\,\ldots n\$. I~want to know if the upper bound of \$4n^2\$ steps, proved in that exercise, is optimum. This Monte Carlo program computes a number \$c\$ such that \$c(n-1)\$ random adjacent comparators would have sufficed to complete the sorting. This number is the sum of \$1/t_k\$ during the \$n\choose2\$ steps of sorting, where \$t\$ is the number of adjacent out-of-order pairs before the \$k\$th step. If \$c\$ is consistently less than \$4n\$, the exercise's upper bound is too high. In fact, ten experiments with \$n=10000\$ all gave \$19904 #include #include "gb_flip.h" int *perm; int *list; int seed; /* random number seed */ int n; /* this many elements */ main(argc,argv) int argc; char *argv[]; { register int i,j,k,t,x,y; register double s; @; @; while (t) @; @; } @ @= if (argc!=3 || sscanf(argv[1],"%d",&n)!=1 || sscanf(argv[2],"%d",&seed)!=1) { fprintf(stderr,"Usage: %s n seed\n",argv[0]); exit(-1); } @ We maintain the following invariants: the indices |i| where |perm[i]>perm[i+1]| are |list[j]| for \$0\le j= gb_init_rand(seed); perm=(int*)malloc(4*(n+2)); list=(int*)malloc(4*(n-1)); for (k=1;k<=n;k++) perm[k]=n+1-k; perm[0]=0;@+perm[n+1]=n+1; for (k=1;k= { s+=1.0/(double)t; j=gb_unif_rand(t); i=list[j]; t--; list[j]=list[t]; x=perm[i];@+y=perm[i+1]; perm[i]=y;@+perm[i+1]=x; if (perm[i-1]>y && perm[i-1]y) list[t++]=i+1; } @ Is this program simple, or what? @= printf("%g = %gn\n",s,s/(double)n); @* Index.