IT++ Logo Newcom Logo

sort.h

Go to the documentation of this file.
00001 
00033 #ifndef SORT_H
00034 #define SORT_H
00035 
00036 #include <itpp/base/vec.h>
00037 
00038 
00039 namespace itpp {
00040 
00045   template<class T>
00046   void sort(Vec<T> &data)
00047   {
00048     QS(0,data.size()-1,data);
00049   }
00050 
00056   template<class T>
00057   ivec sort_index(const Vec<T> &data)
00058   {
00059     int N=data.length(),i;
00060     ivec indexlist(N);
00061 
00062     for(i=0;i<N;i++) {
00063       indexlist(i)=i;
00064     }
00065     QSindex(0,N-1,indexlist,data);
00066     return indexlist;
00067   }
00068 
00079   template<class T>
00080   void QS(int low, int high, Vec<T> &data)
00081   {
00082     int plow, phigh;
00083     T a,test;
00084 
00085     if (high>low) {
00086       a=data[low];
00087       plow=low;
00088       phigh=high;
00089       test=data[phigh];
00090       while (plow<phigh) {
00091         if (test<a) {
00092           data[plow]=test;
00093           plow++;
00094           test=data[plow];
00095         } else {
00096           data[phigh]=test;
00097           phigh--;
00098           test=data[phigh];
00099         }
00100       }
00101       data[plow]=a;
00102       QS(low,plow-1,data);
00103       QS(plow+1,high,data);
00104     }
00105   }
00106 
00119   template<class T>
00120   void QSindex(int low, int high, ivec &indexlist, const Vec<T> &data)
00121   {
00122     int plow,phigh,testindex,aindex;
00123     T a,test;
00124 
00125     if (high>low) {
00126       aindex=indexlist[low];
00127       a=data[aindex];
00128       plow=low;
00129       phigh=high;
00130       testindex=indexlist[phigh];
00131       test=data[testindex];
00132       while (plow<phigh) {
00133         if (test<a) {
00134           indexlist[plow]=testindex;
00135           plow++;
00136           testindex=indexlist[plow];
00137           test=data[testindex];
00138         } else {
00139           indexlist[phigh]=testindex;
00140           phigh--;
00141           testindex=indexlist[phigh];
00142           test=data[testindex];
00143         }
00144       }
00145       indexlist[plow]=aindex;
00146       QSindex(low,plow-1,indexlist,data);
00147       QSindex(plow+1,high,indexlist,data);
00148     }
00149   }
00150 
00151 } // namespace itpp
00152 
00153 #endif // #ifndef SORT_H
00154 
SourceForge Logo

Generated on Wed Apr 18 11:19:58 2007 for IT++ by Doxygen 1.5.2