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