00001 
00002 /*-----------------------------------------------------------------------------
00003   Generic qsort functions.  To generate, you must
00004     1) #define STYPE    datatypetobesorted
00005     2) #define SLT(a,b) (a<b)  must not evaluate a,b more than once!
00006     3) #define SNAME    nameoffunctiontobecreated
00007     4) #include "cs_qsort_template.h"
00008   Then you can call qsort_nameoffunctiontobecreated( int n , STYPE *a )
00009 -------------------------------------------------------------------------------*/
00010 
00011 #ifndef STYPE
00012 # error "STYPE macro not defined"
00013 #endif
00014 
00015 #ifndef SLT
00016 # error "SLT macro not defined"
00017 #endif
00018 
00019 #ifndef SNAME
00020 # error "SNAME macro not defined"
00021 #endif
00022 
00023 #ifndef TWO_TWO
00024 # define TWO_ONE(x,y) x ## y
00025 # define TWO_TWO(x,y) TWO_ONE(x,y)
00026 #endif
00027 
00028 #define ISORT_NAME TWO_TWO(isort_,SNAME)
00029 #define QSREC_NAME TWO_TWO(qsrec_,SNAME)
00030 #define QSORT_NAME TWO_TWO(qsort_,SNAME)
00031 
00032 /********************************************************************************/
00033 /* insertion_sort : sort an array of STYPE                                      */
00034 
00035 static void ISORT_NAME( int n , STYPE * ar )
00036 {
00037    register int  j , p ;  /* array indices */
00038    STYPE temp ;           /* a[j] holding place */
00039    register STYPE *a = ar ;
00040 
00041    if( n < 2 ) return ;
00042 
00043    for( j=1 ; j < n ; j++ ){
00044 
00045      if( SLT(a[j],a[j-1]) ){   /* out of order */
00046         p    = j ;
00047         temp = a[j] ;
00048 
00049        do{
00050           a[p] =  a[p-1] ; /* at this point, a[p-1] > temp, so move it up */
00051           p-- ;
00052        } while( p > 0 && SLT(temp,a[p-1]) ) ;
00053 
00054         a[p] = temp ;       /* finally, put temp in its place */
00055      }
00056    }
00057 }
00058 
00059 /********************************************************************************/
00060 /* qsrec : recursive part of quicksort (stack implementation)                   */
00061 
00062 #ifndef QS_STACK
00063 # define QS_STACK  1024  /* stack size */
00064 #endif
00065 
00066 #define QS_SWAPF(x,y) ( temp=(x),(x)=(y),(y)= temp)
00067 #define QS_SWAPI(i,j) (itemp=(i),(i)=(j),(j)=itemp)
00068 
00069 static void QSREC_NAME( int n , STYPE * ar , int cutoff )
00070 {
00071    register int i , j ;       /* scanning indices */
00072    STYPE temp , pivot ;       /* holding places */
00073    register STYPE *a = ar ;
00074    int itemp ;
00075 
00076    int left , right , mst , stack[QS_STACK] , nnew ;
00077 
00078    /* return if too short (insertion sort will clean up) */
00079 
00080    if( cutoff < 3 ) cutoff = 3 ;
00081    if( n < cutoff ) return ;
00082 
00083    /* initialize stack to start with whole array */
00084 
00085    stack[0] = 0   ;
00086    stack[1] = n-1 ;
00087    mst      = 2   ;
00088 
00089    /* loop while the stack is nonempty */
00090 
00091    while( mst > 0 ){
00092       right = stack[--mst] ;  /* work on subarray from left..right */
00093       left  = stack[--mst] ;
00094 
00095       i = ( left + right ) / 2 ;        /* middle of subarray */
00096 
00097       /* sort the left, middle, and right a[]'s */
00098 
00099       if( SLT(a[i],a[left])     ){ QS_SWAPF(a[left] ,a[i]    ); }
00100       if( SLT(a[right],a[left]) ){ QS_SWAPF(a[left] ,a[right]); }
00101       if( SLT(a[right],a[left]) ){ QS_SWAPF(a[right],a[i]    ); }
00102 
00103       pivot = a[i] ;                    /* a[i] is the median-of-3 pivot */
00104       a[i]  = a[right] ;
00105 
00106       i = left ;                        /* initialize scanning */
00107       j = right ;
00108 
00109       /*----- partition:  move elements bigger than pivot up and elements
00110                           smaller than pivot down, scanning in from ends -----*/
00111 
00112       do{
00113         for( ; SLT(a[++i],pivot) ; ) ;  /* scan i up,   until a[i] >= pivot */
00114         for( ; SLT(pivot,a[--j]) ; ) ;  /* scan j down, until a[j] <= pivot */
00115 
00116         if( j <= i ) break ;            /* if j meets i, quit */
00117 
00118         QS_SWAPF( a[i] , a[j] ) ;       /* put a[i], a[j] into correct halves */
00119       } while( 1 ) ;
00120 
00121       /*----- at this point, the array is partitioned -----*/
00122 
00123       a[right]  = a[i] ;                /* restore the pivot */
00124       a[i]      = pivot ;
00125 
00126       /*----- push subarrays [left..i-1] and [i+1..right] onto stack, if big -----*/
00127 
00128       nnew = 0 ;
00129       if( (i-left)  > cutoff ){ stack[mst++] = left; stack[mst++] = i-1  ; nnew++; }
00130       if( (right-i) > cutoff ){ stack[mst++] = i+1 ; stack[mst++] = right; nnew++; }
00131 
00132       /* if just added two subarrays to stack, make sure shorter one comes first */
00133 
00134       if( nnew == 2 && stack[mst-3] - stack[mst-4] > stack[mst-1] - stack[mst-2] ){
00135          QS_SWAPI( stack[mst-4] , stack[mst-2] ) ;
00136          QS_SWAPI( stack[mst-3] , stack[mst-1] ) ;
00137       }
00138 
00139    }  /* end of while stack is non-empty */
00140 }
00141 
00142 /********************************************************************************/
00143 /* quick_sort :  sort an array partially recursively, and partially insertion   */
00144 
00145 #ifndef QS_CUTOFF
00146 # define QS_CUTOFF 10
00147 #endif
00148 
00149 void QSORT_NAME( int n , STYPE *a )
00150 {
00151    QSREC_NAME( n , a , QS_CUTOFF ) ;
00152    ISORT_NAME( n , a ) ;
00153 }
00154 
00155 #undef ISORT_NAME
00156 #undef QSREC_NAME
00157 #undef QS_SWAPF
00158 #undef QS_SWAPI