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 {
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
SourceForge Logo

Generated on Thu Apr 23 20:06:46 2009 for IT++ by Doxygen 1.5.8