home *** CD-ROM | disk | FTP | other *** search
/ Piper's Pit BBS/FTP: ibm 0010 - 0019 / ibm0010-0019 / ibm0010.tar / ibm0010 / CODE4-1.ZIP / SOURCE.ZIP / U4SORT.C < prev    next >
Encoding:
C/C++ Source or Header  |  1989-10-14  |  2.0 KB  |  105 lines
  1. /* u4sort.c   (c)Copyright Sequiter Software Inc., 1987, 1988, 1989. All rights reserved.
  2.  
  3.    Unfortunately, the 'qsort' routine in the Microsoft Library 
  4.    can give very poor worst case performance.  This routine
  5.    can be used as a replacement.
  6. */
  7.  
  8. #include "d4base.h"
  9.  
  10. #include <string.h>
  11.  
  12. static  size_t  w ;
  13. static  int  (*c)() ;
  14. static  char  *small, *large ;
  15. static  char  flip_buffer[MAX_KEY_SIZE+4] ;
  16.  
  17. static  void  flip(char*, char *) ;
  18. static  void  quick_sort( char *, size_t ) ;
  19.  
  20. static void  flip( a,b ) 
  21. char  *a ;
  22. char  *b ;
  23. {
  24.    memcpy( flip_buffer, a, w ) ;
  25.    memcpy( a, b, w ) ;
  26.    memcpy( b, flip_buffer, w ) ;
  27. }
  28.  
  29.  
  30. static void quick_sort( base, num )
  31. char     *base ;
  32. size_t    num ;
  33. {
  34.    size_t   num_smaller ;
  35.  
  36.    if ( num < 3 ) 
  37.    {
  38.       if ( num == 2 ) 
  39.      if ( (*c)( base, base+w ) > 0 ) 
  40.         flip( base, base+w ) ;
  41.       return ;
  42.    }
  43.  
  44.    large =  base+  w*(num-1) ;
  45.    small =  base+  w*(num>>1) ;
  46.  
  47.    /* base should point to a middle value fewest recursions */
  48.    if ( (*c)( small, large )  > 0 )   flip( small, large ) ;
  49.    if ( (*c)( small, base ) > 0 )
  50.       flip( small, base ) ;
  51.    else
  52.       if ( (*c)( base, large ) > 0 )
  53.      flip( base, large ) ;
  54.  
  55.    if ( num == 3 )
  56.    {
  57.       flip( base, small ) ;
  58.       return ;
  59.    }
  60.  
  61.    small =  base + w ;
  62.  
  63.    while ( small < large )
  64.    {
  65.       if ( (*c)( small, base ) < 0 )
  66.       {
  67.      small += w ;
  68.      continue ;
  69.       }
  70.  
  71.       do
  72.       {
  73.      if ( (*c)(base, large) > 0 ) 
  74.      {
  75.         flip( small, large ) ;
  76.         large -= w ;
  77.         small += w ;
  78.         break ;
  79.      }
  80.      large -= w ;
  81.       } while( small < large ) ;
  82.    }
  83.  
  84.    if ( (*c)(small,base) < 0 )   flip(small,base) ;
  85.    num_smaller =  (size_t) ((small-base) / w) ;
  86.  
  87.    quick_sort( small, num-num_smaller ) ;
  88.    quick_sort( base, num_smaller ) ;
  89.  
  90.    return ;
  91. }
  92.  
  93.  
  94. void  u4sort( base, num, width, compare ) 
  95. void *base ;
  96. size_t  num ;
  97. size_t  width ;
  98. int  (*compare)() ;
  99. {
  100.    w      =  width ;
  101.    c      =  compare ;
  102.    quick_sort( (char *) base, num ) ;
  103. }
  104.  
  105.