xmd Code

/*
xmd - molecular dynamics for metals and ceramics
By Jonathan Rifkin <jon.rifkin@uconn.edu>
Copyright 1995-2004 Jonathan Rifkin

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*/


/*  QUICK SORT ROUTINES  */

/* Global variables (used to reduce number of parameters to */
/* recursive subroutines                                    */

static unsigned *_x;
static unsigned *_u, _xu, _tu;
static int     *_i, _xi, _ti;
static float   *_f, _xf, _tf;
static double  *_d, _xd, _td;
static int      _j;

/* NOTE:  i,_j, lo, hi must be in so that j and hi can be negative  */

/*  UNINDEXED SORT - UNSIGNED  */

void _qsorturec (int lo, int hi)
   {
   int i;
    i=lo;
   _j=hi;
   _xu=_u[(lo+hi)/2];
   while (i<_j)
      {
      while (_u[i]<_xu)
         i++;
      while (_xu<_u[_j])
         _j--;
      if (i<=_j)
         {
         _tu   = _u[i];
         _u[i] = _u[_j];
         _u[_j] = _tu;
         i++;
         _j--;
         }
      }
   if (lo<_j ) _qsorturec (lo, _j );
   if (i < hi) _qsorturec (i , hi);
   }

void sortu (unsigned *z, unsigned n)
   {
   _u = z;
   _qsorturec (0, n-1);
   }

/*  INDEXED SORT - UNSIGNED  */

void _qsortuxrec (int lo, int hi)
   {
   int i;
    i=lo;
   _j=hi;
   _xu=_u[_x[(lo+hi)/2]];
   while (i<_j)
      {
      while (_u[_x[i]]<_xu)
         i++;
      while (_xu<_u[_x[_j]])
         _j--;
      if (i<=_j)
         {
         _tu    = _x[ i];
         _x[ i] = _x[_j];
         _x[_j] = _tu;
         i++;
         _j--;
         }
      }
   if (lo<_j ) _qsortuxrec (lo, _j );
   if (i < hi) _qsortuxrec (i , hi);
   }

void sortux (unsigned *z, unsigned *x, unsigned n)
   {
   _u = z;
   _x = x;
   _qsortuxrec (0, n-1);
   }

/*  INDEXED SORT - SIGNED  */

void _qsortixrec (int lo, int hi)
   {
   int i;
    i=lo;
   _j=hi;
   _xi=_i[_x[(lo+hi)/2]];
   while (i<_j)
      {
      while (_i[_x[i]]<_xi)
         i++;
      while (_xi<_i[_x[_j]])
         _j--;
      if (i<=_j)
         {
         _ti    = _x[ i];
         _x[ i] = _x[_j];
         _x[_j] = _ti;
         i++;
         _j--;
         }
      }
   if (lo<_j ) _qsortixrec (lo, _j );
   if (i < hi) _qsortixrec (i , hi);
   }

void sortix (int *z, unsigned *x, unsigned n)
   {
   _i = z;
   _x = x;
   _qsortixrec (0, n-1);
   }



/*  INDEXED SORT - FLOAT  */

void _qsortfxrec (int lo, int hi)
   {
   int i;
   i=lo;
   _j=hi;
   _xf=_f[_x[(lo+hi)/2]];
   while (i<_j)
      {
      while (_f[_x[i]]<_xf)
         i++;
      while (_xf<_f[_x[_j]])
         _j--;
      if (i<=_j)
         {
         _tf    = _x[ i];
         _x[ i] = _x[_j];
         _x[_j] = _tf;
         i++;
         _j--;
         }
      }
   if (lo<_j ) _qsortfxrec (lo, _j );
   if (i < hi) _qsortfxrec (i , hi);
   }

void sortfx (float *z, unsigned *x, unsigned n)
   {
   _f = z;
   _x = x;
   _qsortfxrec (0, n-1);
   }


/*  INDEXED SORT - DOUBLE  */

void _qsortdxrec (int lo, int hi)
   {
   int i;
    i=lo;
   _j=hi;
   _xd=_d[_x[(lo+hi)/2]];
   while (i<_j)
      {
      while (_d[_x[i]]<_xd)
         i++;
      while (_xd<_d[_x[_j]])
         _j--;
      if (i<=_j)
         {
         _td    = _x[ i];
         _x[ i] = _x[_j];
         _x[_j] = _td;
         i++;
         _j--;
         }
      }
   if (lo<_j ) _qsortdxrec (lo, _j );
   if (i < hi) _qsortdxrec (i , hi);
   }

void sortdx (double *z, unsigned *x, unsigned n)
   {
   _d = z;
   _x = x;
   _qsortdxrec (0, n-1);
   }



#ifdef TEST


#include <stdio.h>
#include <stdlib.h>
#include <conio.h>


int main ()
   {
   unsigned *x;
   double *v, *v0;
   unsigned i;
   unsigned n;

   printf ("Enter n: "); scanf ("%i", &n); printf ("\n");

   x  = (unsigned *) calloc (n, sizeof(unsigned));
   v  = (double   *) calloc (n, sizeof(unsigned));
   v0 = (double   *) calloc (n, sizeof(unsigned));

   for (i=0;i<n;i++)
      {
      x[i] = i;
      v0[i] = v[i] = rand();
      }

   printf ("Hit enter to begin homemade qsort.\n");
   getch();
   sortdx (v, x, n);
   printf ("Sort completed.\n");
   getch();
   for (i=0;i<n;i++)
      printf ("%8i %8i %8lf\n", i, x[i], v[x[i]]);


   return(0);
   }
#endif