home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 June / SIMTEL_0692.cdr / msdos / c / help.arc / SSORT.C < prev    next >
Text File  |  1988-03-10  |  1KB  |  43 lines
  1. /*    SSORT.C        Works just like qsort() except that a shell
  2.  *            sort, rather than a quick sort, is used. This
  3.  *    is more efficient than quicksort for small numbers of elements
  4.  *    and it's not recursive so will use much less stack space.
  5.  *    This routine started out as the one in K&R.
  6.  *
  7.  *    12/13/85:  Modified to select a gap from the series
  8.  *           1, 4, 13, 40, 121 ... as per Knuth.
  9.  *
  10.  *    Copyright (C) 1985, Allen I. Holub.  All rights reserved
  11.  */
  12.  
  13. void    ssort( base, nel, width, cmp )
  14. char    *base;
  15. int    nel, width;
  16. int    (*cmp)();
  17. {
  18.     register int    i, j;
  19.     int        gap, k, tmp ;
  20.     char        *p1, *p2;
  21.  
  22.     for( gap=1; gap <= nel; gap = 3*gap + 1 )
  23.         ;
  24.  
  25.     for( gap /= 3;  gap > 0  ; gap /= 3 )
  26.         for( i = gap; i < nel; i++ )
  27.             for( j = i-gap; j >= 0 ; j -= gap )
  28.             {
  29.                 p1 = base + ( j      * width);
  30.                 p2 = base + ((j+gap) * width);
  31.  
  32.                 if( (*cmp)( p1, p2 ) <= 0 )
  33.                     break;
  34.  
  35.                 for( k = width; --k >= 0 ;)
  36.                 {
  37.                     tmp   = *p1;
  38.                     *p1++ = *p2;
  39.                     *p2++ = tmp;
  40.                 }
  41.             }
  42. }
  43.