Doxygen Source Code Documentation
Main Page Alphabetical List Data Structures File List Data Fields Globals Search
cs_sort_ii.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_intint( int n , int * ar , int * iar )
00013 {
00014 register int j , p ;
00015 register int temp ;
00016 register int itemp ;
00017 register int * 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] ){
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_intint( int n , int * ar , int * iar , int cutoff )
00048 {
00049 register int i , j ;
00050 register int temp , pivot ;
00051 register int itemp , ipivot ;
00052 register int * a = ar ;
00053 register int * ia = iar ;
00054
00055 int left , right , mst , stack[QS_STACK] , nnew ;
00056
00057
00058
00059 if( cutoff < 3 ) cutoff = 3 ;
00060 if( n < cutoff ) return ;
00061
00062
00063
00064 stack[0] = 0 ;
00065 stack[1] = n-1 ;
00066 mst = 2 ;
00067
00068
00069
00070 while( mst > 0 ){
00071 right = stack[--mst] ;
00072 left = stack[--mst] ;
00073
00074 i = ( left + right ) / 2 ;
00075
00076
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] ;
00083 a[i] = a[right] ;
00084 ipivot = ia[i] ;
00085 ia[i] = ia[right] ;
00086
00087 i = left ;
00088 j = right ;
00089
00090
00091
00092
00093 do{
00094 for( ; a[++i] < pivot ; ) ;
00095 for( ; a[--j] > pivot ; ) ;
00096
00097 if( j <= i ) break ;
00098
00099 QS_SWAPF( a[i] , a[j] ) ; QS_SWAPI( ia[i] , ia[j] ) ;
00100 } while( 1 ) ;
00101
00102
00103
00104 a[right] = a[i] ;
00105 a[i] = pivot ;
00106 ia[right] = ia[i] ;
00107 ia[i] = ipivot ;
00108
00109
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
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 }
00123
00124 }
00125
00126
00127
00128
00129 #ifndef QS_CUTOFF
00130 #define QS_CUTOFF 10
00131 #endif
00132
00133 void qsort_intint( int n , int * a , int * ia )
00134 {
00135 qsrec_intint( n , a , ia , QS_CUTOFF ) ;
00136 isort_intint( n , a , ia ) ;
00137 return ;
00138 }