home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_08_08 / 8n08073a < prev    next >
Text File  |  1990-07-18  |  4KB  |  127 lines
  1.  
  2. /*
  3.  * Copyright (C) 1989, Mark R. Nelson
  4.  *
  5.  * This routines sorts an integer array, data[], that has
  6.  * size elements.  It is used as a boilerplate function
  7.  * for a Quicksort, and is intended to replace the ANSI
  8.  * qsort() routine.
  9.  *
  10.  */
  11.  
  12. #define SMALLEST_PARTITION 15
  13.  
  14. my_qsort( int *data, int size )
  15. {
  16.     register int i;
  17.     register int j;
  18.     int first;
  19.     int last;
  20.     int temp;
  21.     int stack_pointer;
  22.     struct {
  23.             int left;
  24.             int right;
  25.            } stack[100];
  26.  
  27. /*
  28.  * The stack structure is used to hold a list of left and
  29.  * right pairs.  These pairs define partitions that still
  30.  * need to be sorted.  When the stack pointer drops below
  31.  * zero, it means all the quicksort partitions have been
  32.  * done.
  33.  */
  34.     stack_pointer = 0;
  35.     stack[0].left = 0;
  36.     stack[0].right = size-1;
  37. /*
  38.  * The while loop below here is the Quicksort partitioning
  39.  * code. It runs until there are no more (left,right)
  40.  * pairs left on the stack.  When it is complete, the
  41.  * insertion sort over the whole array still needs to be
  42.  * done.
  43.  */
  44.     while (stack_pointer>=0)
  45.     {
  46.         first = stack[stack_pointer].left;
  47.         last = stack[stack_pointer].right;
  48.         stack_pointer--;
  49. /*
  50.  * Here is where I swap the first and middle records, in
  51.  * hopes of finding a good key.
  52.  */
  53.         temp = data[ first ];
  54.         data[first] = data[ (last+first)/2 ];
  55.         data[ (last+first)/2 ] = temp;
  56. /*
  57.  * The while loop here is the main loop of the Quicksort.
  58.  * It moves i up and j down until j is positioned at
  59.  * the correct spot where data[0] belongs.  There may
  60.  * or my not be some exchanges along the way.
  61.  */
  62.         i = first+1;
  63.         j = last;
  64.         while ( i <= j )
  65.         {
  66.             while ( data[i] <= data[first] && i <= last )
  67.                 i++;
  68.             while ( data[j] >= data[first] && j > first )
  69.                 j--;
  70.             if ( j > i )
  71.             {
  72.                 temp = data[i];
  73.                 data[i] = data[j];
  74.                 data[j] = temp;
  75.             }
  76.         }
  77. /*
  78.  * At this point, j is pointing to the final position in
  79.  * the array for data[first].  After an exchange, data[j]
  80.  * is set, and will not have to be moved again, ever.
  81.  */
  82.         temp = data[first];
  83.         data[first] = data[j];
  84.         data[j] = temp;
  85. /*
  86.  * After the partitioning is complete, there are two
  87.  * smaller partitions that may need to have a Quicksort
  88.  * performed on them.  This is done here.  A good
  89.  * programmer would probably check for stack overflow here.
  90.  */
  91.         if ( (j-first) >= SMALLEST_PARTITION )
  92.         {
  93.             stack[++stack_pointer].left = first;
  94.             stack[stack_pointer].right = j-1;
  95.         }
  96.         if ( (last-j) >= SMALLEST_PARTITION )
  97.         {
  98.             stack[++stack_pointer].left = j+1;
  99.             stack[stack_pointer].right = last;
  100.         }
  101.     }
  102. /*
  103.  *  When we reach this point, the Quicksort portion of the rou-
  104.  *  tine is complete, and it is time for the insertion sort.
  105.  */
  106.     for ( i=1 ; i<size ; i++ )
  107.     {
  108.         temp = data[i];
  109.         j = i-1;
  110.         while ( j >= 0 )
  111.         {
  112.             if ( data[j] > temp )
  113.             {
  114.                 data[j+1] = data[j];
  115.                 j--;
  116.             }
  117.             else
  118.                 break;
  119.         }
  120.         data[j+1] = temp;
  121.     }
  122. }
  123.  
  124.                     The Final Version of my_qsort()
  125.                               Figure 17
  126.  
  127.