hyper.c

   1 static void hyper_sort(int base,int number,void (*makesmaller)())
   2 {
   3   int i;
   4   if (number==1) return;
   5   for (i=0;i<(number/2);i++)
   6     makesmaller(base+i,base+i+((number+1)/2));
   7
   8   hyper_sort(base+number/2,(number+1)/2,makesmaller);
   9   hyper_sort(base,number - (number+1)/2,makesmaller);
  10 }
  11
  12
  13 static void batchers_sort(int baseP,int N,void (*makesmaller)())
  14 {
  15   int   p, initq, q, r, d, x;
  16
  17   for (p=1; (1<<(p+1))<=N+1; p++);
  18   p = 1<<p;
  19
  20   for (initq=p; p>0; p/=2)
  21     {
  22       q = initq;
  23       r = 0;
  24       d = p;
  25       do
  26         {
  27           for (x=0; x<N-d; x++)
  28             if ( (x & p) == r)
  29               makesmaller(baseP+x,baseP+x+d);
  30           d = q - p;
  31           q /= 2;
  32           r = p;
  33         } while (q != p/2);
  34     }
  35 }
  36
  37 #define MAX_STEPS 10000
  38 struct pair {
  39   int n1,n2,step;
  40 };
  41
  42 struct pair steps[MAX_STEPS];
  43
  44 static int N=0;
  45
  46 void makesmaller(int n1,int n2)
  47 {
  48   steps[N].n1 = n1;
  49   steps[N].n2 = n2;
  50   steps[N].step = N;
  51   N++;
  52 }
  53
  54
  55 int conflict(struct pair *p,int step)
  56 {
  57   int i;
  58   for (i=0;i<N;i++)
  59     if (step == steps[i].step &&
  60         (steps[i].n1 == p->n1 ||
  61          steps[i].n1 == p->n2 ||
  62          steps[i].n2 == p->n1 ||
  63          steps[i].n2 == p->n2))
  64       return(1);
  65   return(0);
  66 }
  67
  68 void reduce()
  69 {
  70   int changed;
  71
  72   do {
  73     int i;
  74     changed = 0;
  75
  76     for (i=0;i<N;i++) {
  77       if (steps[i].step>0 && !conflict(&steps[i],steps[i].step-1)) {
  78         steps[i].step--;
  79         changed=1;
  80       }
  81     }
  82
  83   } while (changed);
  84 }
  85
  86
  87 int comparison(struct pair *p1,struct pair *p2)
  88 {
  89   if (p1->step != p2->step) return(p1->step - p2->step);
  90   if (p1->n1 != p2->n1) return(p1->n1 - p2->n1);
  91   if (p1->n2 != p2->n2) return(p1->n2 - p2->n2);
  92   return(0);
  93 }
  94
  95 void printout()
  96 {
  97   int i;
  98   int step=0;
  99   for (i=0;i<N;i++) {
 100     if (steps[i].step != step) {
 101       printf("\n");
 102       step++;
 103     }
 104     printf("%d:  %d %d\n",steps[i].step,steps[i].n1,steps[i].n2);
 105   }
 106   printf("\n%d steps\n",step+1);
 107 }
 108
 109
 110 main(int argc,char *argv[])
 111 {
 112   batchers_sort(0,atoi(argv[1]),makesmaller);
 113
 114   reduce();
 115
 116   qsort(&steps[0],N,sizeof(struct pair),comparison);
 117
 118   printout();
 119 }