Doxygen Source Code Documentation
cs_sort_di.c File Reference
#include "cs.h"
Go to the source code of this file.
Defines | |
#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_doubleint (int n, double *ar, int *iar) |
void | qsrec_doubleint (int n, double *ar, int *iar, int cutoff) |
void | qsort_doubleint (int n, double *a, int *ia) |
Define Documentation
|
Definition at line 130 of file cs_sort_di.c. Referenced by qsort_doubleint(). |
|
Definition at line 43 of file cs_sort_di.c. Referenced by qsrec_doubleint(). |
|
Definition at line 44 of file cs_sort_di.c. Referenced by qsrec_doubleint(), qsrec_floatfloat(), qsrec_floatint(), qsrec_floatstuff(), qsrec_intint(), and QSREC_NAME(). |
|
Definition at line 45 of file cs_sort_di.c. Referenced by qsrec_double(), qsrec_doubleint(), qsrec_floatfloat(), qsrec_floatint(), qsrec_floatstuff(), qsrec_intint(), and QSREC_NAME(). |
Function Documentation
|
Definition at line 12 of file cs_sort_di.c. Referenced by qsort_doubleint().
00013 { 00014 register int j , p ; /* array indices */ 00015 register double temp ; /* a[j] holding place */ 00016 register int itemp ; 00017 register double * a = ar ; 00018 register int * ia = iar ; 00019 00020 if( n < 2 ) return ; 00021 00022 for( j=1 ; j < n ; j++ ){ 00023 00024 if( a[j] < a[j-1] ){ /* out of order */ 00025 p = j ; 00026 temp = a[j] ; itemp = ia[j] ; 00027 00028 do{ 00029 a[p] = a[p-1] ; /* at this point, a[p-1] > temp, so move it up */ 00030 ia[p] = ia[p-1] ; 00031 p-- ; 00032 } while( p > 0 && temp < a[p-1] ) ; 00033 00034 a[p] = temp ; /* finally, put temp in its place */ 00035 ia[p] = itemp ; 00036 } 00037 } 00038 } |
|
Definition at line 133 of file cs_sort_di.c. References a, isort_doubleint(), QS_CUTOFF, and qsrec_doubleint().
00134 { 00135 qsrec_doubleint( n , a , ia , QS_CUTOFF ) ; 00136 isort_doubleint( n , a , ia ) ; 00137 return ; 00138 } |
|
Definition at line 47 of file cs_sort_di.c. References a, i, left, QS_STACK, QS_SWAPF, QS_SWAPI, and right. Referenced by qsort_doubleint().
00048 { 00049 register int i , j ; /* scanning indices */ 00050 register double temp , pivot ; /* holding places */ 00051 register int itemp , ipivot ; 00052 register double * a = ar ; 00053 register int * ia = iar ; 00054 00055 int left , right , mst , stack[QS_STACK] , nnew ; 00056 00057 /* return if too short (insertion sort will clean up) */ 00058 00059 if( cutoff < 3 ) cutoff = 3 ; 00060 if( n < cutoff ) return ; 00061 00062 /* initialize stack to start with whole array */ 00063 00064 stack[0] = 0 ; 00065 stack[1] = n-1 ; 00066 mst = 2 ; 00067 00068 /* loop while the stack is nonempty */ 00069 00070 while( mst > 0 ){ 00071 right = stack[--mst] ; /* work on subarray from left -> right */ 00072 left = stack[--mst] ; 00073 00074 i = ( left + right ) / 2 ; /* middle of subarray */ 00075 00076 /* sort the left, middle, and right a[]'s */ 00077 00078 if( a[left] > a[i] ){ QS_SWAPF(a[left] ,a[i] ); QS_SWAPI(ia[left] ,ia[i] ); } 00079 if( a[left] > a[right] ){ QS_SWAPF(a[left] ,a[right]); QS_SWAPI(ia[left] ,ia[right]); } 00080 if( a[i] > a[right] ){ QS_SWAPF(a[right],a[i] ); QS_SWAPI(ia[right],ia[i] ); } 00081 00082 pivot = a[i] ; /* a[i] is the median-of-3 pivot! */ 00083 a[i] = a[right] ; 00084 ipivot = ia[i] ; 00085 ia[i] = ia[right] ; 00086 00087 i = left ; /* initialize scanning */ 00088 j = right ; 00089 00090 /*----- partition: move elements bigger than pivot up and elements 00091 smaller than pivot down, scanning in from ends -----*/ 00092 00093 do{ 00094 for( ; a[++i] < pivot ; ) ; /* scan i up, until a[i] >= pivot */ 00095 for( ; a[--j] > pivot ; ) ; /* scan j down, until a[j] <= pivot */ 00096 00097 if( j <= i ) break ; /* if j meets i, quit */ 00098 00099 QS_SWAPF( a[i] , a[j] ) ; QS_SWAPI( ia[i] , ia[j] ) ; 00100 } while( 1 ) ; 00101 00102 /*----- at this point, the array is partitioned -----*/ 00103 00104 a[right] = a[i] ; /*restore the pivot*/ 00105 a[i] = pivot ; 00106 ia[right] = ia[i] ; 00107 ia[i] = ipivot ; 00108 00109 /*----- push subarrays [left..i-1] and [i+1..right] onto stack, if big -----*/ 00110 00111 nnew = 0 ; 00112 if( (i-left) > cutoff ){ stack[mst++] = left ; stack[mst++] = i-1 ; nnew++ ; } 00113 if( (right-i) > cutoff ){ stack[mst++] = i+1 ; stack[mst++] = right ; nnew++ ; } 00114 00115 /* if just added two subarrays to stack, make sure shorter one comes first */ 00116 00117 if( nnew == 2 && stack[mst-3] - stack[mst-4] > stack[mst-1] - stack[mst-2] ){ 00118 QS_SWAPI( stack[mst-4] , stack[mst-2] ) ; 00119 QS_SWAPI( stack[mst-3] , stack[mst-1] ) ; 00120 } 00121 00122 } /* end of while stack is non-empty */ 00123 00124 } |