home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c160 / 1.ddi / SOURCE / U4SORT_Q.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-06-22  |  3.4 KB  |  160 lines
  1.  
  2. /* (c)Copyright Sequiter Software Inc., 1987-1990. All rights reserved.
  3.  
  4.    u4sort_q.c   
  5.  
  6.    Itteritive Quick Sort Algorithm
  7.  
  8.    This algorithm is superior to the more traditional recursive
  9.    Quick Sort as the worst case stack size is proportional to 'log(n)'.
  10.    In this algorithm the stack is explicitly maintained.
  11.  
  12.    In the recursive algorithm, the worst case depth of recursion
  13.    proportional to 'n'.  For example, if there were 1000 items to
  14.    sort, the Quick Sort could, in the worst case, call itself
  15.    1000 times.
  16. */
  17.  
  18. #include "d4all.h"
  19. #include "p4misc.h"
  20. #include <string.h>
  21.  
  22. char    H_PTR H_PTR  ptr_ptr ;
  23. static  int      compare_width ;
  24. static  char  H_PTR  flip_data ;
  25.  
  26.  
  27. static void  flip( long,long ) ;
  28.  
  29. static void  flip( long i, long j )
  30. {
  31.    flip_data  =  ptr_ptr[i] ;
  32.    ptr_ptr[i] =  ptr_ptr[j] ;
  33.    ptr_ptr[j] =  flip_data ;
  34. }
  35.  
  36. static int  v4greater_rc = 1 ;
  37. static int  v4less_rc    = 0 ;
  38. /*
  39. static int  v4bcd_cmp    = 0 ; */
  40.  
  41.  
  42. static int  greater( long,long ) ;
  43.  
  44. static int  greater( long i, long j )
  45. {
  46.    int  rc ;
  47.  
  48.    #ifdef OS2
  49.       rc = u4huge_cmp( ptr_ptr[i], ptr_ptr[j], compare_width ) ;
  50.    #else
  51.       #ifdef LANGUAGE
  52.          rc = u4memcmp( (unsigned char *) ptr_ptr[i], (unsigned char *) ptr_ptr[j], (size_t) compare_width ) ;
  53.       #else
  54.          rc = memcmp( (void *) ptr_ptr[i], (void *) ptr_ptr[j], (size_t) compare_width ) ;
  55.       #endif
  56.    #endif
  57.    if ( rc > 0 )  return v4greater_rc ;
  58.  
  59.    if ( rc == 0 )
  60.       if ( ptr_ptr[i] > ptr_ptr[j] )  return v4greater_rc ;
  61.  
  62.    return v4less_rc ;
  63. }
  64.  
  65.  
  66. void  u4sort_quick( char H_PTR H_PTR pointer_ptr, long n, int width )
  67. {
  68.    /* A stack size of 32 is enough to sort four billion items. */
  69.    long    stack_start[32], stack_end[32], f, l, num, j, i, middle ;
  70.    int     stack_on ;
  71.  
  72.    u4huge_set( pointer_ptr[n], (int) 0xFF, (long) width ) ;
  73.  
  74.    ptr_ptr =  pointer_ptr ;
  75.    compare_width  =  width ;
  76.  
  77.    stack_on       =  0 ;
  78.    stack_start[0] =  0 ;
  79.    stack_end[0]   =  n - 1 ;
  80.  
  81.    while( stack_on >= 0 )
  82.    {
  83.       f =  stack_start[stack_on] ;
  84.       l =  stack_end[stack_on] ;
  85.       stack_on-- ;
  86.  
  87.       /* Sort items 'f' to 'l' */
  88.       while ( f < l )
  89.       {
  90.          /* Pick the middle item based on a sample of 3 items. */
  91.          num =  l - f ;
  92.      if ( num < 2 )
  93.      {
  94.               if ( num == 1 )
  95.         {
  96.            /* Two Items */
  97.            if ( greater(f,l) )
  98.               flip(f,l) ;
  99.         }
  100.         break ;
  101.      }
  102.  
  103.      /* Choose 'ptr_ptr[f]' to be a median of three values */
  104.      middle =  (l+f) / 2 ;
  105.  
  106.      if ( greater(middle,l) )
  107.         flip(middle,l) ;
  108.  
  109.      if ( greater(middle,f) )
  110.         flip(f,middle) ;
  111.      else
  112.           if ( greater(f,l) )
  113.            flip(f,l) ;
  114.  
  115.      if ( num == 2 )   /* Special Optimization on Three Items */
  116.      {
  117.         flip(f,middle) ;
  118.         break ;
  119.      }
  120.  
  121.      i = f + 1 ;
  122.      while( greater(f,i) )  i++ ;
  123.  
  124.      j =  l ;
  125.      while( greater(j,f) )  j-- ;
  126.  
  127.      while ( i<j )
  128.      {
  129.         flip( i,j ) ;
  130.         i++ ;
  131.  
  132.            while( greater(f,i) )  i++ ;
  133.         j-- ;
  134.  
  135.            while( greater(j,f) )  j-- ;
  136.      }
  137.  
  138.      flip( f,j ) ;
  139.  
  140.      /* Both Sides are non-trivial */
  141.      if ( j-f > l-j )
  142.      {
  143.         /* Left sort is larger, put it on the stack */
  144.         stack_start[++stack_on] =  f ;
  145.         stack_end[stack_on]     =  j-1 ;
  146.  
  147.         f = j+ 1 ;
  148.      }
  149.      else
  150.      {
  151.         /* Right sort is larger, put it on the stack */
  152.         stack_start[++stack_on] =  j+1 ;
  153.         stack_end[stack_on]     =  l ;
  154.  
  155.         l = j- 1 ;
  156.      }
  157.       }
  158.    }
  159. }
  160.