Doxygen Source Code Documentation
Main Page Alphabetical List Data Structures File List Data Fields Globals Search
cs_sort_ff.c
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007 #include "cs.h"
00008
00009
00010
00011
00012 static void isort_floatfloat( int n , float * ar , float * iar )
00013 {
00014 register int j , p ;
00015 register float temp ;
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] ){
00025 p = j ;
00026 temp = a[j] ; itemp = ia[j] ;
00027
00028 do{
00029 a[p] = a[p-1] ;
00030 ia[p] = ia[p-1] ;
00031 p-- ;
00032 } while( p > 0 && temp < a[p-1] ) ;
00033
00034 a[p] = temp ;
00035 ia[p] = itemp ;
00036 }
00037 }
00038 }
00039
00040
00041
00042
00043 #define QS_STACK 1024
00044 #define QS_SWAPF(x,y) ( temp=(x),(x)=(y),(y)= temp)
00045 #define QS_SWAPI(i,j) (itemp=(i),(i)=(j),(j)=itemp)
00046
00047 static void qsrec_floatfloat( int n , float * ar , float * iar , int cutoff )
00048 {
00049 register int i , j ;
00050 register float temp , pivot ;
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
00059
00060 if( cutoff < 3 ) cutoff = 3 ;
00061 if( n < cutoff ) return ;
00062
00063
00064
00065 stack[0] = 0 ;
00066 stack[1] = n-1 ;
00067 mst = 2 ;
00068
00069
00070
00071 while( mst > 0 ){
00072 right = stack[--mst] ;
00073 left = stack[--mst] ;
00074
00075 i = ( left + right ) / 2 ;
00076
00077
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] ;
00084 a[i] = a[right] ;
00085 ipivot = ia[i] ;
00086 ia[i] = ia[right] ;
00087
00088 i = left ;
00089 j = right ;
00090
00091
00092
00093
00094 do{
00095 for( ; a[++i] < pivot ; ) ;
00096 for( ; a[--j] > pivot ; ) ;
00097
00098 if( j <= i ) break ;
00099
00100 QS_SWAPF( a[i] , a[j] ) ; QS_SWAPF( ia[i] , ia[j] ) ;
00101 } while( 1 ) ;
00102
00103
00104
00105 a[right] = a[i] ;
00106 a[i] = pivot ;
00107 ia[right] = ia[i] ;
00108 ia[i] = ipivot ;
00109
00110
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
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 }
00124
00125 }
00126
00127
00128
00129
00130 #ifndef QS_CUTOFF
00131 #define QS_CUTOFF 10
00132 #endif
00133
00134 void qsort_floatfloat( int n , float * a , float * ia )
00135 {
00136 qsrec_floatfloat( n , a , ia , QS_CUTOFF ) ;
00137 isort_floatfloat( n , a , ia ) ;
00138 return ;
00139 }