00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028 #ifndef MAT_SORT
00029 #define MAT_SORT
00030 namespace mat {
00031
00032 #if 1
00033
00034 template<class Treal>
00035 void quicksort(const Treal* value, int* index, int low, int high)
00036 throw(std::exception){
00037 if(high >= low)
00038 {
00039 int i = low;
00040 int j = high;
00041 int tmp;
00042 Treal pivot = value[index[(low + high) / 2]];
00043 do {
00044 while (value[index[i]] < pivot) i++;
00045 while (value[index[j]] > pivot) j--;
00046 if (i <= j) {
00047 tmp = index[i];
00048 index[i] = index[j];
00049 index[j] = tmp;
00050 i++;
00051 j--;
00052 }
00053 } while (i <= j);
00054 if(low < j) quicksort(value, index, low, j);
00055 if(i < high) quicksort(value, index, i, high);
00056 }
00057 }
00058
00059 #else
00060
00061
00062 template<typename Treal, typename Tfun>
00063 void quicksort(Tfun const & fun, int* index, int low, int high)
00064 throw(std::exception){
00065 int i = low;
00066 int j = high;
00067 int tmp;
00068 Treal pivot = fun.value(index[(low + high) / 2]);
00069 do {
00070 while (fun.value(index[i]) < pivot) i++;
00071 while (fun.value(index[j]) > pivot) j--;
00072 if (i <= j) {
00073 tmp = index[i];
00074 index[i] = index[j];
00075 index[j] = tmp;
00076 i++;
00077 j--;
00078 }
00079 } while (i <= j);
00080
00081 if(low < j) quicksort<Treal>(fun, index, low, j);
00082 if(i < high) quicksort<Treal>(fun, index, i, high);
00083 }
00084
00085 template<class Treal>
00086 void quicksort(const Treal* value, int* index, int low, int high) {
00087 int i = low;
00088 int j = high;
00089 int tmp;
00090 Treal pivot = value[index[(low + high) / 2]];
00091 do {
00092 while (value[index[i]] < pivot) i++;
00093 while (value[index[j]] > pivot) j--;
00094 if (i <= j) {
00095 tmp = index[i];
00096 index[i] = index[j];
00097 index[j] = tmp;
00098 i++;
00099 j--;
00100 }
00101 } while (i <= j);
00102 if(low < j) quicksort(value, index, low, j);
00103 if(i < high) quicksort(value, index, i, high);
00104 }
00105
00106 #endif
00107
00108 }
00109
00110 #endif