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