00001
00002 #ifndef __Sort_hh__
00003 #define __Sort_hh__
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064 #include <assert.h>
00065
00066
00067
00068 template <class T>
00069 static inline void sortSwap (T* a, int i, int j) {
00070 T tmp = a[i]; a[i] = a[j]; a[j] = tmp;
00071 }
00072 template <class T>
00073 static inline int sortCmp (T* a, int i, int j) {
00074 if (a[i] < a[j]) { return -1; }
00075 if (a[i] > a[j]) { return 1; }
00076 return 0;
00077 }
00078
00079
00080
00081 template <class Closure>
00082 inline void
00083 __insertionSort (Closure cl, int start, int n)
00084 {
00085 for (int i = start; i < start+n-1; i++) {
00086 for (int j = i+1; j > start; j--) {
00087 if (sortCmp(cl,j-1,j) <= 0) { break; }
00088 sortSwap(cl,j-1,j);
00089 }
00090 }
00091 }
00092
00093
00094
00095 template <class Closure>
00096 inline void
00097 __selectionSort1 (Closure cl, int start, int n)
00098 {
00099 for (int i = start; i < start + n - 1; i++) {
00100
00101 if (i > start && sortCmp(cl,i,i-1) == 0) { continue; }
00102
00103 int minLoc = i;
00104 for (int j = i + 1; j < start + n; j++) {
00105 if (sortCmp(cl,j,minLoc) < 0) {
00106 minLoc = j;
00107 }
00108 }
00109 if (minLoc > i) {
00110 sortSwap (cl, i, minLoc);
00111 }
00112 }
00113 }
00114
00115
00116
00117 template <class Closure>
00118 inline void
00119 __selectionSort2 (Closure cl, int start, int n)
00120 {
00121 int i = start;
00122 int j = start + n - 1;
00123 while (i < j) {
00124
00125 if (i > start && sortCmp(cl,i,i-1) == 0) { i++; continue; }
00126 if (j < start+n-1 && sortCmp(cl,j,j+1) == 0) { j--; continue; }
00127
00128 int minLoc=i, maxLoc=i;
00129 for (int k = i + 1; k <= j; k++) {
00130 if (sortCmp(cl,k,minLoc) < 0) { minLoc = k; }
00131 if (sortCmp(cl,k,maxLoc) > 0) { maxLoc = k; }
00132 }
00133
00134
00135 if (minLoc == maxLoc) { break; }
00136 if (minLoc > maxLoc) {
00137 sortSwap(cl,minLoc,maxLoc);
00138 int tmp=minLoc; minLoc=maxLoc; maxLoc=tmp;
00139 }
00140 if (minLoc > i) { sortSwap(cl,i,minLoc); }
00141 if (maxLoc < j) { sortSwap(cl,j,maxLoc); }
00142 i++; j--;
00143 }
00144 }
00145
00146
00147
00148
00149 template <class Closure>
00150 inline int
00151 __3median (Closure cl, int x, int y, int z)
00152 {
00153 return sortCmp(cl,x,y) > 0
00154 ? (sortCmp(cl,y,z) > 0
00155 ? y : (sortCmp(cl,x,z) > 0 ? z : x))
00156 : (sortCmp(cl,y,z) < 0
00157 ? y : (sortCmp(cl,x,z) < 0 ? z : x));
00158 }
00159
00160
00161
00162 template <class Closure>
00163 inline void
00164 __quickSort (Closure cl, int start, int n)
00165 {
00166
00167 if (n < 16) {
00168 __insertionSort (cl, start, n);
00169
00170
00171 return;
00172 }
00173
00174
00175
00176 int x = start + (n >> 2);
00177 int y = start + (n >> 1);
00178 int z = x + (n >> 1);
00179 int pivotLoc = __3median (cl, x, y, z);
00180 sortSwap (cl, start, pivotLoc);
00181
00182
00183
00184
00185
00186
00187
00188
00189
00190
00191 int pivot = start;
00192 int left = start + 1;
00193 int right = start + n - 1;
00194 while (1) {
00195 restart:
00196 while (left <= right) {
00197 int c = sortCmp (cl, left, pivot);
00198 if (c > 0) { break; }
00199 if (c < 0) { left++; continue; }
00200 if (left != pivot+1) { sortSwap (cl, left, pivot+1); }
00201 pivot++; left++;
00202 }
00203 while (left <= right) {
00204 int c = sortCmp (cl, right, pivot);
00205 if (c < 0) { break; }
00206 if (c > 0) { right--; continue; }
00207 #ifdef __DEBUG__
00208 assert (left < right);
00209 #endif
00210 sortSwap (cl, left, right);
00211 if (left != pivot+1) { sortSwap (cl, left, pivot+1); }
00212 pivot++; left++; right--;
00213 goto restart;
00214 }
00215 if (left > right) { break; }
00216 sortSwap (cl, left, right);
00217 }
00218
00219 #ifdef __DEBUG__
00220 assert (pivot >= start);
00221 assert (right >= pivot);
00222 assert (left == right + 1);
00223 assert (left <= start + n);
00224 #endif
00225 int numEq = pivot - start + 1;
00226 int numLt = right - pivot;
00227 int numLe = left - start;
00228 int numGt = n - numLe;
00229
00230 #ifdef __DEBUG__
00231 assert (numEq + numLt + numGt == n);
00232 #endif
00233
00234 int count = (numEq < numLt) ? numEq : numLt;
00235 int dist = numLe - count;
00236 for (int i = 0; i < count; i++) {
00237 sortSwap (cl, start + i, start + i + dist);
00238 }
00239
00240
00241 if (numLt > 0) { __quickSort (cl, start, numLt); }
00242 if (numGt > 0) { __quickSort (cl, left, numGt); }
00243 }
00244
00245
00246 template <class Closure>
00247 inline void
00248 sort (Closure cl, int n)
00249 {
00250 __quickSort (cl, 0, n);
00251 #ifdef __DEBUG__
00252
00253 for (int i = 1; i < n; i++) {
00254 assert (sortCmp (cl, i-1, i) <= 0);
00255 }
00256 #endif
00257
00258 }
00259
00260 #endif // __Sort_hh__