00001 00030 #ifndef SORT_H 00031 #define SORT_H 00032 00033 #include <itpp/base/vec.h> 00034 #include <itpp/base/converters.h> 00035 #include <itpp/base/math/log_exp.h> 00036 00037 00038 namespace itpp { 00039 00048 enum SORTING_METHOD { INTROSORT = 0, QUICKSORT = 1, HEAPSORT = 2, 00049 INSERTSORT = 3 }; 00050 00097 template<class T> 00098 class Sort { 00099 public: 00101 Sort(SORTING_METHOD method = INTROSORT): sort_method(method) {} 00102 00104 void set_method(SORTING_METHOD method) { sort_method = method; } 00105 00107 SORTING_METHOD get_method() const { return sort_method; } 00108 00116 void sort(int low, int high, Vec<T> &data); 00117 00125 ivec sort_index(int low, int high, const Vec<T> &data); 00126 00140 void intro_sort(int low, int high, int max_depth, Vec<T> &data); 00141 00155 ivec intro_sort_index(int low, int high, int max_depth, 00156 const Vec<T> &data); 00157 00158 private: 00159 SORTING_METHOD sort_method; 00160 00161 void IntroSort(int low, int high, int max_depth, T data[]); 00162 void IntroSort_Index(int low, int high, int max_depth, int indexlist[], 00163 const T data[]); 00164 00165 void QuickSort(int low, int high, T data[]); 00166 void QuickSort_Index(int low, int high, int indexlist[], const T data[]); 00167 00168 void HeapSort(int low, int high, T data[]); 00169 void HeapSort_Index(int low, int high, int indexlist[], const T data[]); 00170 00171 void InsertSort(int low, int high, T data[]); 00172 void InsertSort_Index(int low, int high, int indexlist[], const T data[]); 00173 }; 00174 00175 00184 template<class T> 00185 void sort(Vec<T> &data, SORTING_METHOD method = INTROSORT) 00186 { 00187 Sort<T> s(method); 00188 s.sort(0, data.size()-1, data); 00189 } 00190 00200 template<class T> 00201 ivec sort_index(const Vec<T> &data, SORTING_METHOD method = INTROSORT) 00202 { 00203 Sort<T> s(method); 00204 return s.sort_index(0, data.size()-1, data); 00205 } 00206 00207 00208 // ---------------------------------------------------------------------- 00209 // Public functions for various sorting methods 00210 // ---------------------------------------------------------------------- 00211 00212 template<class T> 00213 void Sort<T>::sort(int low, int high, Vec<T> &data) 00214 { 00215 int N = data.size(); 00216 00217 it_assert((low >= 0) && (high > low) && (high < N), "Sort::sort(): " 00218 "low or high out of bounds"); 00219 00220 switch (sort_method) { 00221 case INTROSORT: 00222 IntroSort(low, high, levels2bits(N), data._data()); 00223 break; 00224 case QUICKSORT: 00225 QuickSort(low, high, data._data()); 00226 break; 00227 case HEAPSORT: 00228 HeapSort(low, high, data._data()); 00229 break; 00230 case INSERTSORT: 00231 InsertSort(low, high, data._data()); 00232 break; 00233 default: 00234 it_error("Sort<T>::sort(): Unknown sorting method"); 00235 } 00236 } 00237 00238 00239 template<class T> 00240 ivec Sort<T>::sort_index(int low, int high, const Vec<T> &data) 00241 { 00242 int N = data.size(); 00243 00244 it_assert((low >= 0) && (high > low) && (high < N), "Sort::sort(): " 00245 "low or high out of bounds"); 00246 00247 ivec indexlist(N); 00248 for(int i = 0; i < N; ++i) { 00249 indexlist(i) = i; 00250 } 00251 00252 switch (sort_method) { 00253 case INTROSORT: 00254 IntroSort_Index(low, high, levels2bits(N), indexlist._data(), 00255 data._data()); 00256 break; 00257 case QUICKSORT: 00258 QuickSort_Index(low, high, indexlist._data(), data._data()); 00259 break; 00260 case HEAPSORT: 00261 HeapSort_Index(low, high, indexlist._data(), data._data()); 00262 break; 00263 case INSERTSORT: 00264 InsertSort_Index(low, high, indexlist._data(), data._data()); 00265 break; 00266 default: 00267 it_error("Sort<T>::sort_index(): Unknown sorting method"); 00268 } 00269 00270 return indexlist; 00271 } 00272 00273 00274 // INTRO SORT 00275 template<class T> 00276 void Sort<T>::intro_sort(int low, int high, int max_depth, Vec<T> &data) 00277 { 00278 it_assert((low >= 0) && (high > low) && (high < data.size()), 00279 "Sort::sort(): low or high out of bounds"); 00280 IntroSort(low, high, max_depth, data._data()); 00281 } 00282 00283 // INTRO SORT INDEX 00284 template<class T> 00285 ivec Sort<T>::intro_sort_index(int low, int high, int max_depth, 00286 const Vec<T> &data) 00287 { 00288 int N = data.size(); 00289 it_assert((low >= 0) && (high > low) && (high < N), 00290 "Sort::sort(): low or high out of bounds"); 00291 00292 ivec indexlist(N); 00293 for (int i = 0; i < N; ++i) { 00294 indexlist(i) = i; 00295 } 00296 00297 IntroSort_Index(low, high, max_depth, indexlist._data(), data._data()); 00298 00299 return indexlist; 00300 } 00301 00302 00303 // ---------------------------------------------------------------------- 00304 // Private functions for sorting methods 00305 // ---------------------------------------------------------------------- 00306 00307 template<class T> 00308 void Sort<T>::IntroSort(int low, int high, int max_depth, T data[]) 00309 { 00310 if (high-low > 16) { 00311 max_depth--; 00312 if (max_depth == 0) { 00313 HeapSort(low, high, data); 00314 return; 00315 } 00316 00317 if (high>low) { 00318 T a = data[low]; 00319 int plow = low; 00320 int phigh = high; 00321 T test = data[phigh]; 00322 while (plow < phigh) { 00323 if (test < a) { 00324 data[plow] = test; 00325 plow++; 00326 test = data[plow]; 00327 } else { 00328 data[phigh] = test; 00329 phigh--; 00330 test = data[phigh]; 00331 } 00332 } 00333 data[plow] = a; 00334 IntroSort(low,plow-1,max_depth,data); 00335 IntroSort(plow+1,high,max_depth,data); 00336 return; 00337 } 00338 } else { 00339 InsertSort(low, high, data); 00340 return; 00341 } 00342 } 00343 00344 template<class T> 00345 void Sort<T>::IntroSort_Index(int low, int high, int max_depth, 00346 int indexlist[], const T data[]) 00347 { 00348 if (high-low > 16) { 00349 max_depth--; 00350 if (max_depth == 0) { 00351 HeapSort_Index(low, high, indexlist, data); 00352 return; 00353 } 00354 00355 if (high > low) { 00356 int aindex = indexlist[low]; 00357 T a = data[aindex]; 00358 int plow = low; 00359 int phigh = high; 00360 int testindex = indexlist[phigh]; 00361 T test = data[testindex]; 00362 while (plow < phigh) { 00363 if (test < a) { 00364 indexlist[plow] = testindex; 00365 plow++; 00366 testindex = indexlist[plow]; 00367 test = data[testindex]; 00368 } else { 00369 indexlist[phigh] = testindex; 00370 phigh--; 00371 testindex = indexlist[phigh]; 00372 test = data[testindex]; 00373 } 00374 } 00375 indexlist[plow] = aindex; 00376 IntroSort_Index(low,plow-1,max_depth,indexlist,data); 00377 IntroSort_Index(plow+1,high,max_depth,indexlist,data); 00378 } 00379 } else { 00380 InsertSort_Index(low, high, indexlist, data); 00381 return; 00382 } 00383 } 00384 00385 template <class T> 00386 void Sort<T>::QuickSort(int low, int high, T data[]) 00387 { 00388 if (high > low) { 00389 T a = data[low]; 00390 int plow = low; 00391 int phigh = high; 00392 T test = data[phigh]; 00393 while (plow < phigh) { 00394 if (test < a) { 00395 data[plow] = test; 00396 plow++; 00397 test = data[plow]; 00398 } else { 00399 data[phigh] = test; 00400 phigh--; 00401 test = data[phigh]; 00402 } 00403 } 00404 data[plow] = a; 00405 QuickSort(low,plow-1,data); 00406 QuickSort(plow+1,high,data); 00407 } 00408 } 00409 00410 template<class T> 00411 void Sort<T>::QuickSort_Index(int low, int high, int indexlist[], 00412 const T data[]) 00413 { 00414 if (high > low) { 00415 int aindex = indexlist[low]; 00416 T a = data[aindex]; 00417 int plow = low; 00418 int phigh = high; 00419 int testindex = indexlist[phigh]; 00420 T test = data[testindex]; 00421 while (plow < phigh) { 00422 if (test < a) { 00423 indexlist[plow] = testindex; 00424 plow++; 00425 testindex = indexlist[plow]; 00426 test = data[testindex]; 00427 } else { 00428 indexlist[phigh] = testindex; 00429 phigh--; 00430 testindex = indexlist[phigh]; 00431 test = data[testindex]; 00432 } 00433 } 00434 indexlist[plow] = aindex; 00435 QuickSort_Index(low,plow-1,indexlist,data); 00436 QuickSort_Index(plow+1,high,indexlist,data); 00437 } 00438 } 00439 00440 template<class T> 00441 void Sort<T>::HeapSort(int low, int high, T data[]) 00442 { 00443 int size=(high+1)-low; 00444 int i=size/2; 00445 T temp; 00446 while(1) { 00447 if (i > 0) 00448 temp = data[--i + low]; 00449 else { 00450 if (size-- == 0) 00451 break; 00452 temp = data[size + low]; 00453 data[size + low] = data[low]; 00454 } 00455 00456 int parent = i; 00457 int child = i*2 + 1; 00458 00459 while (child < size) { 00460 if (child + 1 < size && data[child + 1 + low] > data[child + low]) 00461 child++; 00462 if (data[child + low] > temp) { 00463 data[parent + low] = data[child + low]; 00464 parent = child; 00465 child = parent*2 + 1; 00466 } else 00467 break; 00468 } 00469 data[parent + low] = temp; 00470 } 00471 } 00472 00473 template<class T> 00474 void Sort<T>::HeapSort_Index(int low, int high, int indexlist[], 00475 const T data[]) 00476 { 00477 int size=(high+1)-low; 00478 int i=size/2; 00479 00480 while(1) { 00481 T tempValue; 00482 int tempIndex; 00483 if (i > 0) { 00484 i--; 00485 tempValue = data[indexlist[i + low]]; 00486 tempIndex = indexlist[i + low]; 00487 } else { 00488 if (size-- == 0) 00489 break; 00490 tempValue = data[indexlist[size + low]]; 00491 tempIndex = indexlist[size + low]; 00492 indexlist[size+low] = indexlist[low]; 00493 } 00494 00495 int parent = i; 00496 int child = i*2 + 1; 00497 00498 while (child < size) { 00499 if ((child + 1 < size) 00500 && data[indexlist[child + 1 + low]] > data[indexlist[child + low]]) 00501 child++; 00502 if (data[indexlist[child + low]] > tempValue) { 00503 indexlist[parent + low] = indexlist[child + low]; 00504 parent = child; 00505 child = parent*2 + 1; 00506 } else 00507 break; 00508 } 00509 indexlist[parent + low] = tempIndex; 00510 } 00511 } 00512 00513 template<class T> 00514 void Sort<T>::InsertSort(int low, int high, T data[]) 00515 { 00516 for(int i = low+1; i <= high; i++) { 00517 T value = data[i]; 00518 int j; 00519 for (j = i - 1; j >= low && data[j] > value; j--) { 00520 data[j + 1] = data[j]; 00521 } 00522 data[j + 1] = value; 00523 } 00524 } 00525 00526 template<class T> 00527 void Sort<T>::InsertSort_Index(int low, int high, int indexlist[], 00528 const T data[]) 00529 { 00530 for(int i = low + 1; i <= high; i++) { 00531 T value = data[indexlist[i]]; 00532 int tempIndex = indexlist[i]; 00533 int j; 00534 for (j = i - 1; j >= low && data[indexlist[j]] > value; j--) { 00535 indexlist[j + 1] = indexlist[j]; 00536 } 00537 indexlist[j + 1] = tempIndex; 00538 } 00539 } 00540 00541 00542 } // namespace itpp 00543 00544 #endif // #ifndef SORT_H
Generated on Sat May 3 16:10:41 2008 for IT++ by Doxygen 1.5.5