1 #include <string.h>
2
3 #include "cs.h"
4
5 /********************************************************************************/
6 /* insertion_sort : sort an array of string + void* */
7
8 #undef BEFORE
9 #undef AFTER
10 #undef EQUALS
11 #define BEFORE(a,b) ( strcmp((a),(b)) < 0 )
12 #define AFTER(a,b) ( strcmp((a),(b)) > 0 )
13 #define EQUALS(a,b) ( strcmp((a),(b)) == 0 )
14
isort_string_void(int n,char ** ar,void ** iar)15 static void isort_string_void( int n , char **ar , void **iar )
16 {
17 register int j , p ; /* array indices */
18 register char *temp ; /* a[j] holding place */
19 register void *itemp ;
20 register char **a = ar ;
21 register void **ia = iar ;
22
23 if( n < 2 ) return ;
24
25 for( j=1 ; j < n ; j++ ){
26
27 if( BEFORE(a[j],a[j-1]) ){ /* out of order */
28 p = j ;
29 temp = a[j] ; itemp = ia[j] ;
30
31 do{
32 a[p] = a[p-1] ; /* at this point, a[p-1] > temp, so move it up */
33 ia[p] = ia[p-1] ;
34 p-- ;
35 } while( p > 0 && temp < a[p-1] ) ;
36
37 a[p] = temp ; /* finally, put temp in its place */
38 ia[p] = itemp ;
39 }
40 }
41 }
42
43 /********************************************************************************/
44 /* qsrec : recursive part of quicksort (stack implementation) */
45
46 #undef QS_SWAPF
47 #undef QS_SWAPI
48 #undef QS_SWAPV
49 #define QS_SWAPS(x,y) ( temp=(x),(x)=(y),(y)= temp)
50 #define QS_SWAPI(i,j) (itemp=(i),(i)=(j),(j)=itemp)
51 #define QS_SWAPV(i,j) (vtemp=(i),(i)=(j),(j)=vtemp)
52 #ifndef QS_STACK
53 # define QS_STACK 9999
54 #endif
55
qsrec_string_void(int n,char ** ar,void ** iar,int cutoff)56 static void qsrec_string_void( int n , char **ar , void **iar , int cutoff )
57 {
58 register int i , j ; /* scanning indices */
59 register char *temp , *pivot ; /* holding places */
60 register void *ipivot ;
61 register char **a = ar ;
62 register void **ia = iar ;
63 int itemp ;
64 void *vtemp ;
65
66 int left , right , mst , stack[QS_STACK] , nnew ;
67
68 /* return if too short (insertion sort will clean up) */
69
70 if( cutoff < 3 ) cutoff = 3 ;
71 if( n < cutoff ) return ;
72
73 /* initialize stack to start with whole array */
74
75 stack[0] = 0 ;
76 stack[1] = n-1 ;
77 mst = 2 ;
78
79 /* loop while the stack is nonempty */
80
81 while( mst > 0 ){
82 right = stack[--mst] ; /* work on subarray from left -> right */
83 left = stack[--mst] ;
84
85 i = ( left + right ) / 2 ; /* middle of subarray */
86
87 /* sort the left, middle, and right a[]'s */
88
89 if( AFTER(a[left],a[i]) ){ QS_SWAPS(a[left] ,a[i] ); QS_SWAPV(ia[left] ,ia[i] ); }
90 if( AFTER(a[left],a[right]) ){ QS_SWAPS(a[left] ,a[right]); QS_SWAPV(ia[left] ,ia[right]); }
91 if( AFTER(a[i],a[right]) ){ QS_SWAPS(a[right],a[i] ); QS_SWAPV(ia[right],ia[i] ); }
92
93 pivot = a[i] ; /* a[i] is the median-of-3 pivot! */
94 a[i] = a[right] ;
95 ipivot = ia[i] ;
96 ia[i] = ia[right] ;
97
98 i = left ; /* initialize scanning */
99 j = right ;
100
101 /*----- partition: move elements bigger than pivot up and elements
102 smaller than pivot down, scanning in from ends -----*/
103
104 do{
105 for( ; BEFORE(a[++i],pivot) ; ) ; /* scan i up, until a[i] >= pivot */
106 for( ; AFTER(a[--j],pivot) ; ) ; /* scan j down, until a[j] <= pivot */
107
108 if( j <= i ) break ; /* if j meets i, quit */
109
110 QS_SWAPS( a[i] , a[j] ) ; QS_SWAPV( ia[i] , ia[j] ) ;
111 } while( 1 ) ;
112
113 /*----- at this point, the array is partitioned -----*/
114
115 a[right] = a[i] ; /*restore the pivot*/
116 a[i] = pivot ;
117 ia[right] = ia[i] ;
118 ia[i] = ipivot ;
119
120 /*----- push subarrays [left..i-1] and [i+1..right] onto stack, if big -----*/
121
122 nnew = 0 ;
123 if( (i-left) > cutoff ){ stack[mst++] = left ; stack[mst++] = i-1 ; nnew++ ; }
124 if( (right-i) > cutoff ){ stack[mst++] = i+1 ; stack[mst++] = right ; nnew++ ; }
125
126 /* if just added two subarrays to stack, make sure shorter one comes first */
127
128 if( nnew == 2 && stack[mst-3] - stack[mst-4] > stack[mst-1] - stack[mst-2] ){
129 QS_SWAPI( stack[mst-4] , stack[mst-2] ) ;
130 QS_SWAPI( stack[mst-3] , stack[mst-1] ) ;
131 }
132
133 } /* end of while stack is non-empty */
134
135 }
136
137 /********************************************************************************/
138 /* quick_sort : sort an array partially recursively, and partially insertion */
139
140 #ifndef QS_CUTOFF
141 #define QS_CUTOFF 8
142 #endif
143
qsort_string_void(int n,char ** a,void ** ia)144 void qsort_string_void( int n , char **a , void **ia )
145 {
146 qsrec_string_void( n , a , ia , QS_CUTOFF ) ;
147 isort_string_void( n , a , ia ) ;
148 return ;
149 }
150