IT++ Logo

sort.h

Go to the documentation of this file.
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
SourceForge Logo

Generated on Sat Apr 19 10:42:05 2008 for IT++ by Doxygen 1.5.5