DataMuseum.dk

top - download

    Length: 1622 (0x656)
    Types: TextFile
    Names: »sort2.c«

└─⟦87ddcff64⟧ Bits:30001253 CPHDIST85 Tape, 1985 Autumn Conference Copenhagen
    └─ ⟦this⟧ »cph85dist/wirewrap/sort2.c« 

TextFile

/*******************************************************
*  Batcher's method sort by signalname.		       *
*  Reference: Knuth Sorting & Searching, Section 5.2.2 *
*******************************************************/

#include "wirewrap.h"

sort2()
{
struct pin tempin;
int p,q,r,d,n,i,j,m;
int a,b,innera,innerb,outera,outerb;

/*Find the 'middle' of the array.*/
n = nextfree;
i = 1;
j = 2;
while(j < n)
  {
  i = j;
  j = j+j;
  }
m = i;  /*m is the middle of the array*/
        
/* Batcher's method*/
p = m;
while(p > 0)
  {
  q = m;
  r = 0;
  d =p;
  for(;;)
    {
    for(i= 0;i < n-d;i++)
      {
      if ( (i&p) == r)
        if(   (pinarray[i].row >  pinarray[i+d].row) 
          || ((pinarray[i].row == pinarray[i+d].row)
          &&  (pinarray[i].col >  pinarray[i+d].col)))
          {
          /* First decide which two to swap. */
          a=i;
          b=i+d;
          /* Then decide which ones reference them. */
          innera = pinarray[a].inner;
          outera = pinarray[a].outer;
          innerb=pinarray[b].inner;
          outerb=pinarray[b].outer;
          /* Update those. */
          if(innera != -1)pinarray[innera].inner=b;
          if(outera != -1)pinarray[outera].outer=b;
          if(innerb != -1)pinarray[innerb].inner=a;
          if(outerb != -1)pinarray[outerb].outer=a;
          /* Now make the swap. */
          tempin = pinarray[b];
          pinarray[b] = pinarray[a];
          pinarray[a] = tempin;
          }
      }
      if(p != q)
        {
        d = q - p;
        q = q/2;
        r = p;
        }
      else 
        break;
    }
  p = p/2;
  }
}