home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_11_07 / qsort.c < prev    next >
C/C++ Source or Header  |  1993-02-04  |  3KB  |  76 lines
  1. #include <stdlib.h>
  2. #include <string.h>
  3. #include <malloc.h>
  4.  
  5. #define MIN_SIZE 4
  6. #define MEMSWAP( A, B, TEMP, SIZE)   { memcpy( (TEMP), (A), (SIZE));  \
  7.       memcpy( (A), (B), (SIZE));  memcpy( (B), (TEMP), (SIZE));  }
  8.  
  9. int my_qsort( char *data, unsigned n_elements, unsigned element_size,
  10.                      int (*compare)(void *elem1, void *elem2))
  11. {
  12.    unsigned start[18], size[18], n_pieces = 1, curr_size;
  13.    unsigned size1, size2;
  14.    char *startptr, *endptr, *pivot, *tbuff;
  15.    int comp;
  16.  
  17.    tbuff = _alloca( element_size);
  18.    start[0] = 0;
  19.    size[0] = n_elements;
  20.    while( n_pieces)
  21.       {
  22.       pivot = startptr = data + start[n_pieces - 1] * element_size;
  23.       curr_size = size[n_pieces - 1];
  24.       if( curr_size < MIN_SIZE)     /* bubblesort em */
  25.          {
  26.          unsigned i, j;
  27.          char *tptr1, *tptr2;
  28.  
  29.          for( tptr1 = pivot, i = 0; i < curr_size; i++, tptr1 += element_size)
  30.             for( tptr2 = tptr1 + element_size, j = i + 1; j < curr_size;
  31.                                                 j++, tptr2 += element_size)
  32.                if( (compare)(tptr1, tptr2) > 0)
  33.                   MEMSWAP( tptr1, tptr2, tbuff, element_size);
  34.          n_pieces--;
  35.          }
  36.       else
  37.          {
  38.          if( curr_size > 10)
  39.             MEMSWAP( pivot, pivot + (curr_size / 2) * element_size, tbuff,
  40.                         element_size);
  41.          endptr = startptr + (curr_size - 1) * element_size;
  42.          startptr += element_size;
  43.          while( startptr <= endptr)
  44.             {
  45.             comp = (compare)(startptr, pivot);
  46.             if( comp > 0)
  47.                {
  48.                MEMSWAP( endptr, startptr, tbuff, element_size);
  49.                endptr -= element_size;
  50.                }
  51.             else
  52.                startptr += element_size;
  53.             }
  54.          startptr -= element_size;
  55.          MEMSWAP( pivot, startptr, tbuff, element_size);
  56.          size1 = (startptr - pivot) / element_size;
  57.          size2 = curr_size - size1 - 1;
  58.          if( size2 < size1)
  59.             {
  60.             start[n_pieces] = start[n_pieces - 1] + size1 + 1;
  61.             size[n_pieces] = size2;
  62.             size[n_pieces - 1] = size1;
  63.             }
  64.          else
  65.             {
  66.             start[n_pieces] = start[n_pieces - 1];
  67.             start[n_pieces - 1] += size1 + 1;
  68.             size[n_pieces - 1] = size2;
  69.             size[n_pieces] = size1;
  70.             }
  71.          n_pieces++;
  72.          }
  73.       }
  74.    return( 0);
  75. }
  76.