IT++ Logo
sort.h
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
SourceForge Logo

Generated on Sat Jul 9 2011 15:21:30 for IT++ by Doxygen 1.7.4