Doxygen Source Code Documentation
cs_sort_ff.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_floatfloat (int n, float *ar, float *iar) |
void | qsrec_floatfloat (int n, float *ar, float *iar, int cutoff) |
void | qsort_floatfloat (int n, float *a, float *ia) |
Define Documentation
|
Definition at line 131 of file cs_sort_ff.c. Referenced by qsort_floatfloat(). |
|
Definition at line 43 of file cs_sort_ff.c. Referenced by qsrec_floatfloat(). |
|
Definition at line 44 of file cs_sort_ff.c. |
|
Definition at line 45 of file cs_sort_ff.c. |
Function Documentation
|
Definition at line 12 of file cs_sort_ff.c. Referenced by qsort_floatfloat().
00013 { 00014 register int j , p ; /* array indices */ 00015 register float temp ; /* a[j] holding place */ 00016 register float itemp ; 00017 register float * a = ar ; 00018 register float * 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 134 of file cs_sort_ff.c. References a, isort_floatfloat(), QS_CUTOFF, and qsrec_floatfloat(). Referenced by BFIT_bootstrap_sample(), and BFIT_prepare_dataset().
00135 { 00136 qsrec_floatfloat( n , a , ia , QS_CUTOFF ) ; 00137 isort_floatfloat( n , a , ia ) ; 00138 return ; 00139 } |
|
Definition at line 47 of file cs_sort_ff.c. References a, i, left, QS_STACK, QS_SWAPF, QS_SWAPI, and right. Referenced by qsort_floatfloat().
00048 { 00049 register int i , j ; /* scanning indices */ 00050 register float temp , pivot ; /* holding places */ 00051 register float ipivot ; 00052 register float * a = ar ; 00053 register float * ia = iar ; 00054 int itemp ; 00055 00056 int left , right , mst , stack[QS_STACK] , nnew ; 00057 00058 /* return if too short (insertion sort will clean up) */ 00059 00060 if( cutoff < 3 ) cutoff = 3 ; 00061 if( n < cutoff ) return ; 00062 00063 /* initialize stack to start with whole array */ 00064 00065 stack[0] = 0 ; 00066 stack[1] = n-1 ; 00067 mst = 2 ; 00068 00069 /* loop while the stack is nonempty */ 00070 00071 while( mst > 0 ){ 00072 right = stack[--mst] ; /* work on subarray from left -> right */ 00073 left = stack[--mst] ; 00074 00075 i = ( left + right ) / 2 ; /* middle of subarray */ 00076 00077 /* sort the left, middle, and right a[]'s */ 00078 00079 if( a[left] > a[i] ){ QS_SWAPF(a[left] ,a[i] ); QS_SWAPF(ia[left] ,ia[i] ); } 00080 if( a[left] > a[right] ){ QS_SWAPF(a[left] ,a[right]); QS_SWAPF(ia[left] ,ia[right]); } 00081 if( a[i] > a[right] ){ QS_SWAPF(a[right],a[i] ); QS_SWAPF(ia[right],ia[i] ); } 00082 00083 pivot = a[i] ; /* a[i] is the median-of-3 pivot! */ 00084 a[i] = a[right] ; 00085 ipivot = ia[i] ; 00086 ia[i] = ia[right] ; 00087 00088 i = left ; /* initialize scanning */ 00089 j = right ; 00090 00091 /*----- partition: move elements bigger than pivot up and elements 00092 smaller than pivot down, scanning in from ends -----*/ 00093 00094 do{ 00095 for( ; a[++i] < pivot ; ) ; /* scan i up, until a[i] >= pivot */ 00096 for( ; a[--j] > pivot ; ) ; /* scan j down, until a[j] <= pivot */ 00097 00098 if( j <= i ) break ; /* if j meets i, quit */ 00099 00100 QS_SWAPF( a[i] , a[j] ) ; QS_SWAPF( ia[i] , ia[j] ) ; 00101 } while( 1 ) ; 00102 00103 /*----- at this point, the array is partitioned -----*/ 00104 00105 a[right] = a[i] ; /*restore the pivot*/ 00106 a[i] = pivot ; 00107 ia[right] = ia[i] ; 00108 ia[i] = ipivot ; 00109 00110 /*----- push subarrays [left..i-1] and [i+1..right] onto stack, if big -----*/ 00111 00112 nnew = 0 ; 00113 if( (i-left) > cutoff ){ stack[mst++] = left ; stack[mst++] = i-1 ; nnew++ ; } 00114 if( (right-i) > cutoff ){ stack[mst++] = i+1 ; stack[mst++] = right ; nnew++ ; } 00115 00116 /* if just added two subarrays to stack, make sure shorter one comes first */ 00117 00118 if( nnew == 2 && stack[mst-3] - stack[mst-4] > stack[mst-1] - stack[mst-2] ){ 00119 QS_SWAPI( stack[mst-4] , stack[mst-2] ) ; 00120 QS_SWAPI( stack[mst-3] , stack[mst-1] ) ; 00121 } 00122 00123 } /* end of while stack is non-empty */ 00124 00125 } |