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
Generated on Fri Jun 8 01:07:10 2007 for IT++ by Doxygen 1.5.2