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
00029
00035 #ifndef MAT_SORT
00036 #define MAT_SORT
00037 namespace mat {
00038
00039 #if 1
00040
00041 template<class Treal>
00042 void quicksort(const Treal* value, int* index, int low, int high)
00043 {
00044 if(high >= low)
00045 {
00046 int i = low;
00047 int j = high;
00048 int tmp;
00049 Treal pivot = value[index[(low + high) / 2]];
00050 do {
00051 while (value[index[i]] < pivot) i++;
00052 while (value[index[j]] > pivot) j--;
00053 if (i <= j) {
00054 tmp = index[i];
00055 index[i] = index[j];
00056 index[j] = tmp;
00057 i++;
00058 j--;
00059 }
00060 } while (i <= j);
00061 if(low < j) quicksort(value, index, low, j);
00062 if(i < high) quicksort(value, index, i, high);
00063 }
00064 }
00065
00066 #else
00067
00068
00069 template<typename Treal, typename Tfun>
00070 void quicksort(Tfun const & fun, int* index, int low, int high)
00071 throw(std::exception){
00072 int i = low;
00073 int j = high;
00074 int tmp;
00075 Treal pivot = fun.value(index[(low + high) / 2]);
00076 do {
00077 while (fun.value(index[i]) < pivot) i++;
00078 while (fun.value(index[j]) > pivot) j--;
00079 if (i <= j) {
00080 tmp = index[i];
00081 index[i] = index[j];
00082 index[j] = tmp;
00083 i++;
00084 j--;
00085 }
00086 } while (i <= j);
00087
00088 if(low < j) quicksort<Treal>(fun, index, low, j);
00089 if(i < high) quicksort<Treal>(fun, index, i, high);
00090 }
00091
00092 template<class Treal>
00093 void quicksort(const Treal* value, int* index, int low, int high) {
00094 int i = low;
00095 int j = high;
00096 int tmp;
00097 Treal pivot = value[index[(low + high) / 2]];
00098 do {
00099 while (value[index[i]] < pivot) i++;
00100 while (value[index[j]] > pivot) j--;
00101 if (i <= j) {
00102 tmp = index[i];
00103 index[i] = index[j];
00104 index[j] = tmp;
00105 i++;
00106 j--;
00107 }
00108 } while (i <= j);
00109 if(low < j) quicksort(value, index, low, j);
00110 if(i < high) quicksort(value, index, i, high);
00111 }
00112
00113 #endif
00114
00115 }
00116
00117 #endif