Doxygen Source Code Documentation
cs_sort_template.h File Reference
Go to the source code of this file.
Defines | |
| #define | TWO_ONE(x, y) x ## y |
| #define | TWO_TWO(x, y) TWO_ONE(x,y) |
| #define | ISORT_NAME TWO_TWO(isort_,SNAME) |
| #define | QSREC_NAME TWO_TWO(qsrec_,SNAME) |
| #define | QSORT_NAME TWO_TWO(qsort_,SNAME) |
| #define | QS_STACK 1024 |
| #define | QS_SWAPF(x, y) ( temp=(x),(x)=(y),(y)= temp) |
| #define | QS_SWAPI(i, j) (itemp=(i),(i)=(j),(j)=itemp) |
| #define | QS_CUTOFF 10 |
Functions | |
| void | ISORT_NAME (int n, STYPE *ar) |
| void | QSREC_NAME (int n, STYPE *ar, int cutoff) |
| void | QSORT_NAME (int n, STYPE *a) |
Define Documentation
|
|
Definition at line 28 of file cs_sort_template.h. Referenced by QSORT_NAME(). |
|
|
Definition at line 146 of file cs_sort_template.h. Referenced by QSORT_NAME(). |
|
|
Definition at line 63 of file cs_sort_template.h. Referenced by QSREC_NAME(). |
|
|
Definition at line 66 of file cs_sort_template.h. |
|
|
Definition at line 67 of file cs_sort_template.h. |
|
|
Definition at line 30 of file cs_sort_template.h. |
|
|
Definition at line 29 of file cs_sort_template.h. Referenced by QSORT_NAME(). |
|
|
Definition at line 24 of file cs_sort_template.h. |
|
|
Definition at line 25 of file cs_sort_template.h. |
Function Documentation
|
||||||||||||
|
Definition at line 35 of file cs_sort_template.h. References a, p, SLT, and STYPE.
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 }
|
|
||||||||||||
|
Definition at line 149 of file cs_sort_template.h. References a, ISORT_NAME, QS_CUTOFF, QSREC_NAME, and STYPE.
00150 {
00151 QSREC_NAME( n , a , QS_CUTOFF ) ;
00152 ISORT_NAME( n , a ) ;
00153 }
|
|
||||||||||||||||
|
Definition at line 69 of file cs_sort_template.h. References a, i, left, QS_STACK, QS_SWAPF, QS_SWAPI, right, SLT, and STYPE.
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 }
|
