home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / c_spec / sources / ssort.c < prev    next >
Text File  |  1986-02-20  |  1KB  |  72 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.  
  44. #ifdef DEBUG
  45.  
  46. cmp( cpp1, cpp2 )
  47. char    **cpp1, **cpp2;
  48. {
  49.     register int    rval;
  50.     printf("comparing %s to %s ", *cpp1, *cpp2 );
  51.  
  52.     rval = strcmp( *cpp1, *cpp2 );
  53.  
  54.     printf("returning %d\n", rval );
  55.     return rval;
  56. }
  57.  
  58. /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  59.  
  60. main( argc, argv )
  61. int    argc;
  62. char    **argv;
  63. {
  64.     ssort( ++argv, --argc, sizeof(*argv), cmp );
  65.  
  66.     while( --argc >= 0 )
  67.         printf("%s\n", *argv++ );
  68. }
  69.  
  70. #endif
  71.  
  72.